数组中重复的数字题目一

发表于

面试题3：题目一 找出数组中重复的数字

在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2，3，1，0，2，5，3}，那么对应的输出是重复的数字2或者3。

OC形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
...
NSArray *numbers = @[@(2),@(3),@(1),@(0),@(2),@(5),@(3)];
...
- (BOOL)duplicateWithNumbers:(NSMutableArray *)numbers length:(int)length {
    if (!numbers || length <= 0) {
        return NO;
    }
    for (int i = 0; i < length; ++i) {
        if (numbers[i] < 0 || [numbers[i] integerValue] > length - 1) {
            return NO;
        }
    }
    
    for (int i = 0; i < length; ++i) {
        NSInteger j = [numbers[i] integerValue];
        while (j != i) {
            if (j == [numbers[j] integerValue]) {
                self.duplication = j;
                return YES;
            }
            NSInteger temp = j;
            j = [numbers[temp] integerValue];
            numbers[temp] = @(temp);
        }
    }
    return NO;
}

时间复杂度

代码中尽管有一个两重循环，但每个数字最多只要交换两次就能找到属于它自己的位置，因此总的时间复杂度为O(n)，另外所有的操作步骤都是在输入的数组上进行的，不需要额外分配内存，因此空间复杂度为O(1)。

思路

首先想到的都是排序，排序一个长度为n的数组需要O(nlogn)的时间。还可以利用哈希表来解决，从头到尾按顺序扫描数组里的每个数字，每扫描到一个数字的时候，都可以用O(1)的时间来判断哈希表里是否已经包含了该数字。如果哈希表里还没有这个数字，就把它加入哈希表。如果哈希表里已经存在该数字，就找到一个重复的数字。这个算法的时间复杂度为O(n)，但提高时间效率是以一个大小为O(n)的哈希表为代价的。
上述代码中的思路是根据下标和数值重排数组。