数组的查重

对数组的查重判断：

NSArray*array=@[@"12-11",@"12-11",@"12-11",@"12-12",@"12-13",@"12-14"];

第一种方法：开辟新的内存空间，然后判断是否存在，若不存在则添加到数组中，得到最终结果的顺序不发生变化。效率分析：时间复杂度为O ( n2 )：

NSMutableArray*resultArray=[[NSMutableArray alloc]initWithCapacity:array.count];

// 外层一个循环

for(NSString*iteminarray){

// 调用-containsObject:本质也是要循环去判断，因此本质上是双层遍历

// 时间复杂度为O ( n^2 )而不是O (n)

if(![resultArraycontainsObject:item]){

[resultArrayaddObject:item];

}

}

NSLog(@"resultArray: %@",resultArray);

补充：原来集合操作可以通过valueForKeyPath来实现的，去重可以一行代码实现：

array=[arrayvalueForKeyPath:@"@distinctUnionOfObjects.self"];

NSLog(@"%@",array);

第二种方法：利用NSDictionary去重，字典在设置key-value时，若已存在则更新值，若不存在则插入值，然后获取allValues。若不要求有序，则可以采用此种方法。若要求有序，还得进行排序。效率分析：只需要一个循环就可以完成放入字典，若不要求有序，时间复杂度为O(n)。若要求排序，则效率与排序算法有关：

NSMutableDictionary*resultDict=[[NSMutableDictionaryalloc]initWithCapacity:array.count];

for(NSString*iteminarray){

[resultDictsetObject:itemforKey:item];

}

NSArray*resultArray=resultDict.allValues;

NSLog(@"%@",resultArray);

如果需要按照原来的升序排序，可以这样：

resultArray=[resultArraysortedArrayUsingComparator:^NSComparisonResult(id_Nonnullobj1,id_Nonnullobj2){

NSString*item1=obj1;

NSString*item2=obj2;

return[item1compare:item2options:NSLiteralSearch];

}];

NSLog(@"%@",resultArray);

第三种方法：利用集合NSSet的特性(确定性、无序性、互异性)，放入集合就自动去重了。但是它与字典拥有同样的无序性，所得结果顺序不再与原来一样。如果不要求有序，使用此方法与字典的效率应该是差不多的。效率分析：时间复杂度为O (n)：

NSSet*set=[NSSetsetWithArray:array];

NSArray*resultArray=[setallObjects];

NSLog(@"%@",resultArray);

如果要求有序，那就得排序，比如这里要升序排序：

resultArray=[resultArraysortedArrayUsingComparator:^NSComparisonResult(id_Nonnullobj1,id_Nonnullobj2){

NSString*item1=obj1;

NSString*item2=obj2;

return[item1compare:item2options:NSLiteralSearch];

}];

NSLog(@"%@",resultArray);

一直没有使用过有序集合，网友们反馈到可以直接使用有序集合：

NSOrderedSet*set=[NSOrderedSet orderedSetWithArray:array];

NSLog(@"%@",set.array);