在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字，要求时间复杂度为O(n).
简单解法同数组索引的值和值作为索引的值作为比较交换:
//原文地址:http://www.cnblogs.com/xiaofeixiang
-(NSInteger)duplicate:(NSMutableArray *)array{
for (NSInteger i=0;i<[array count];i++) {
while (i!=[array[i] integerValue]) {
if ([array[[array[i] integerValue]] isEqualTo:array[i]]) {
return [array[i] integerValue];
}
NSInteger temp=[array[[array[i] integerValue]] integerValue];
array[[array[i] integerValue]]=array[i];
array[i]=[NSNumber numberWithInteger:temp];
}
}
return -1;
}
测试代码:
NSMutableArray *dataSource=[[NSMutableArray alloc]initWithObjects:@"2",@"3",@"1",@"4",@"1", nil];
NSInteger index=[search duplicate:dataSource];
NSLog(@"重复的数字:%ld",index);
NSLog(@"技术交流群:%@",@"228407086");
还存在另外一种解法，比较简单，很绕，有兴趣的可以研究一下:
-(NSInteger)duplicate:(NSMutableArray *)array{
for (NSInteger i= 0 ; i<[array count]; i++) {
NSInteger index =[array[i] integerValue];
if (index >= [array count]) {ki,k /.m m,l;‘‘j im9l./
index -= [array count];
}
if ([array[index] integerValue] >= [array count]) {
return index;
}
array[index]=[NSNumber numberWithInteger:[array[index] integerValue] + [array count] ];
}
return - 1 ;
}
原文：http://www.cnblogs.com/xiaofeixiang/p/4626697.html