首页 > 编程语言 > 详细

算法-数组中重复的数字

时间:2015-07-07 14:23:52      阅读:278      评论:0      收藏:0      [点我收藏+]

在一个长度为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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!