题目：在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
//原文地址: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;
}
|
测试代码:
|
1
2
3
4
|
NSMutableArray
*dataSource=[[
NSMutableArray
alloc]initWithObjects:@
"2"
,@
"3"
,@
"1"
,@
"4"
,@
"1"
,
nil
];
NSInteger
index=[search duplicate:dataSource];
NSLog
(@
"重复的数字:%ld"
,index);
NSLog
(@
"技术交流群:%@"
,@
"228407086"
);
|
还存在另外一种解法，比较简单，很绕，有兴趣的可以研究一下:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
-(
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 ;
}
|
本文转自Fly_Elephant博客园博客，原文链接：http://www.cnblogs.com/xiaofeixiang/p/4626697.html，如需转载请自行联系原作者
