查找数组中重复的元素

发表于 分类于
本文字数： 1.6k 阅读时长 ≈ 1 分钟

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

解法思路

常规思路

最简单的方法就是用一个集合 set，遍历数组的每一个元素，在 set 中查找是否存在该元素，如果存在则返回；不存在则放入集合，并继续循环。

复杂度：

  • 空间复杂度为：O(N)
  • 时间复杂度为：O(NlogN) （遍历数组为 O(N)，set 中查找为 O(logN)）

代码如下：

1
2
3
4
5
6
7
8
9
10
11
bool duplicate(int numbers[], int n, int* duplication) {
    set<int> Set;
    for (int i = 0; i < numbers.size(); i++){
        if (Set.find(numbers[i]) != Set.end()){
            *duplication = numbers[i];
            return true;
        }
        Set.insert(numbers[i]);
    }
    return false;
}

改进：使用hash表

使用一个长度为 n 的数组来作为 hash 表，初始化为 0。然后遍历数组，利用数组元素作为 hash 表的索引，如果其对应的值为 1，说明是第二次访问该索引，那么该索引就是原数组中重复的元素；如果其对应的值为 0，说明是第一次访问，设置为 1。

复杂度：

  • 空间复杂度为：O(N)
  • 时间复杂度为：O(N)

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
bool duplicate(int numbers[], int length, int* duplication) {
    int hash_table[length];
    for (int i = 0; i < length; i++){
        if (hash_table[numbers[i]] == 1){
            *duplication = numbers[i];
            return true;
        }
        else
            hash_table[numbers[i]] = 1;
    }
    return false;
}

常数空间

上面的方法都会使用 O(N) 的内存空间，如果只能使用 O(1) 的空间，那么可以考虑下面的方法。

一种类似于基数排序的方法：

索引 i 从 0 开始遍历数组，

  • 如果 i == numbers[i]，说明 numbers[i] 在正确的位置上；
  • 如果 i != numbers[i]，
    • 如果 numbers[i] != numbers[numbers[i]]，交换 numbers[i] 和 numbers[numbers[i]]，那么 numbers[numbers[i]] 将会在正确的位置上。
    • 否则 numbers[i] == numbers[numbers[i]]，那么就找到了 numbers[i]。

复杂度：

  • 空间复杂度：O(1)
  • 时间复杂度：O(N)

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool duplicate(int numbers[], int length, int* duplication) {
    for (int i = 0; i < length; ++i){
        while (i != numbers[i]){
            if (numbers[i] == numbers[numbers[i]]){
                *duplication = numbers[i];
                return true;
            }
            else{
                swap(numbers[i], numbers[numbers[i]]);
            }
        }
    }
    return false;
}