Fork me on GitHub

找出数组中重复的数字

发表于 | 分类于 
这是崔斯特的第一百零八篇原创文章

努力、奋斗 (๑• . •๑)

找出数组中重复的数字

题目描述

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

解法

解法一

排序后，顺序扫描，判断是否有重复，时间复杂度为 O(n²)。

解法二

利用哈希表，遍历数组，如果哈希表中没有该元素，则存入哈希表中，否则返回重复的元素。时间复杂度为 O(n)，空间复杂度为 O(n)。

解法三

长度为 n，元素的数值范围也为 n，如果没有重复元素，那么数组每个下标对应的值与下标相等。

从头到尾遍历数组，当扫描到下标 i 的数字 nums[i]：

  • 如果等于 i，继续向下扫描；
  • 如果不等于 i，拿它与第 nums[i] 个数进行比较，如果相等，说明有重复值，返回 nums[i]。如果不相等，就把第 i 个数 和第 nums[i] 个数交换。重复这个比较交换的过程。

此算法时间复杂度为 O(n)，因为每个元素最多只要两次交换，就能确定位置。空间复杂度为 O(1)。

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
28
29
30
31
32
33
34
/**
 * @author zhujian on 2019/12/26.
 */
public class Solution {
    public int findDuplicate(int[] array) {
        if (array.length == 0) {
            return -1;
        }
        for (int i = 0; i < array.length; i++) {
            while (array[i] != i) {
                if (array[i] == array[array[i]]) {
                    return array[i];
                }
                swap(array, i, array[i]);
                System.out.println(Arrays.toString(array));
            }
        }
        return -1;
    }
    private void swap(int[] array, int i, int j) {
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
    public static void main(String[] args) {
        int[] arr = new int[]{2, 3, 1, 0, 2, 5, 3};
        int res = new Solution().findDuplicate(arr);
        System.out.println(res);
    }
}

代码中有一个两重循环，但每个数字最多只要交换两次就可以找到属于自己的位置，因此时间复杂度是O(n)。不需要额外分配内存，空间复杂度是O(1)。

Output

1
2
3
4
[1, 3, 2, 0, 2, 5, 3]
[3, 1, 2, 0, 2, 5, 3]
[0, 1, 2, 3, 2, 5, 3]
2

以数组[2, 3, 1, 0, 2, 5, 3]为例来分析找到重复数字的步骤：

  1. 数组的第 0 个数字（从 0 开始计数，和数组的下标保持一致）是 2，与它的下标不相等，于是把它和下标为 2 的数字 1 交换。交换之后的数组是[1, 3, 2, 0, 2, 5, 3]。
  2. 此时第 0 个数字是 1，仍然与它的下标不相等，继续把它和下标为 1 的数字 3 交换，得到数组[3, 1, 2, 0, 2, 5, 3]
  3. 接下来继续交换第 0 个数字 3 和第 3 个数字 0，得到数组[0, 1, 2, 3, 2, 5, 3]。
  4. 此时第 0 个数字的数值为 0，接着扫描下一个数字。在接下来的几个数字中，下标为 1，2，3 的三个数字分别为 1，2，3 它们的下标和数值都分别相等，因此不需要做任何操作。
  5. 接下来扫描到下标为 4 的数字 2。由于它的数值与它的下标不相等，再比较它和下标为 2 的数字。注意到此时数组中下标为 2 的数字也是 2，也就是数字在下标为 2 和下标为 4 的两个位置都出现了，因此找到一个重复的数字。

本题关键是：在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内并且有重复，这说明数组是可以排序的，把每个数字交换到自己应该在的位置，排序时就能找到重复字段。理想状态下的情况：[0, 1, 2, 3, 4, x, x, x]

Python解法更简单

1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(arr):
    if len(arr) == 0:
        return -1
    for i in range(len(arr)):
        while arr[i] != i:
            tmp = arr[i]
            if tmp == arr[tmp]:
                return tmp
            arr[i], arr[tmp] = arr[tmp], arr[i]
            print(arr)
print(solution([3, 1, 2, 0, 2, 5, 3]))

不修改数组找出重复的数字

题目描述

在一个长度为 n+1 的数组里的所有数字都在 1 到 n 的范围内，数组中至少有一个数字是重复的，请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为 8 的数组 {2, 3, 5, 4, 3, 2, 6, 7}，那么对应的输出是重复的数字 2 或者 3。

解法

解法一

创建长度为 n+1 的辅助数组，把原数组的元素复制到辅助数组中。如果原数组被复制的数是 m，则放到辅助数组第 m 个位置。这样很容易找出重复元素。空间复杂度为 O(n)。

解法二

数组元素的取值范围是 [1, n]，对该范围对半划分，分成 [1, middle], [middle+1, n]。计算数组中有多少个(count)元素落在 [1, middle] 区间内，如果 count 大于 middle，那么说明这个范围内有重复元素，否则在另一个范围内。继续对这个范围对半划分，继续统计区间内元素数量。

时间复杂度 O(n * log n)，空间复杂度 O(1)。

注意，此方法无法找出所有重复的元素。如果左右半区同时存在重复值，先算哪个半区就会先得到哪边的重复值。

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * @author zhujian on 2019/12/26.
 */
public class Solution {
    public int findDuplicate(int[] array) {
        if (array.length == 0) {
            return -1;
        }
        int start = 1;
        int end = array.length - 1;
        while (start <= end) {
            int middle = start + ((end - start) >> 1);
            int count = countRange(array, start, middle);
            if (end == start) {
                if (count > 1) {
                    return start;
                } else {
                    break;
                }
            } else {
                if (count > (middle - start) + 1) {
                    end = middle;
                } else {
                    start = middle + 1;
                }
            }
        }
        return -1;
    }
    private int countRange(int[] array, int start, int end) {
        if (array.length == 0) {
            return -1;
        }
        int count = 0;
        for (int i : array) {
            if (i >= start && i <= end) {
                count++;
            }
        }
        return count;
    }
    public static void main(String[] args) {
        int[] arr = new int[]{2, 3, 5, 4, 3, 2, 6, 7};
        int res = new Solution().findDuplicate(arr);
        System.out.println(res);
    }
}

按照二分法查找的思路，如果输出长度为n的数组，那么函数countRange将被调用O(log n)次，每次需要O(n)时间，因此总的时间复杂度是O(nlog n) ，空间复杂度是O(1)。