《剑指Offer》数组中的重复数字

发表于 2023-03-26 更新于 2024-06-02 分类于剑指Offer 阅读次数：

题目1：数组中的重复数字

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

示例 1：

1 2	输入：documents = [2, 5, 3, 0, 5, 0] 输出：0 或 5

能够想到解法有很多，但是这道题目考验的不止是程序员的算法水平，更多的是和面试官的沟通能力。首先，读题确认题目要求，划重点：数字都在0~n-1之间、输出任意一个重复的数字即可。然后，尝试思考最简单的解决办法，计算出该方法的时间空间复杂度。和面试官沟通，是否需要优化，使用时间（或空间）复杂度更低的算法。

解法一：交换数字

如果 0~n-1 个数字在长度为 n 的数组里并且没有重复，那么一定能够在数组中排序成 [0,1,2, ..., n-1]。遍历原数组，将位置 i 上的数字 j 不断和位置 j 上的数字交换，直到位置 i 上的数字为 i，如果交换的时候发现两个数字相等，那么就说明数组中有重复数字，此时返回结果。

public int findRepeatDocument(int[] documents) {
    int result = -1;
    for (int i = 0; i < documents.length; i++) {
        while (documents[i] != i) {
            if (documents[i] >= documents.length || documents[i] < 0) {
                throw new IllegalArgumentException("数组中包含不在0到n-1中的数字");
            }
            if (documents[documents[i]] == documents[i]) {
                return documents[i];
            }
            int swap = documents[documents[i]];
            documents[documents[i]] = documents[i];
            documents[i] = swap;
        }
    }
    return result;
}

时间复杂度O(n) 空间复杂度O(1)

解法二：排序数组

排序数组之后遍历判断。

public int findRepeatDocument(int[] documents) {
    Arrays.sort(documents);
    int result = -1;
    for (int i = 1; i < documents.length; i++) {
        if (documents[i] == documents[i - 1]) {
            return documents[i];
        }
    }
    return result;
}

时间复杂度O(nlogn) 空间复杂度O(1)

题目2：不修改原数组数组中的重复数字

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

解法一：哈希表

如果面试官不允许修改原数组，那么我们可以考虑使用哈希表保存每个数字的出现次数。如果数组长度不长直接使用数组boolean[]，长度较长就使用HashSet。

public int findRepeatDocument(int[] documents) {
    HashSet<Integer> set = new HashSet<>();
    int result = -1;
    for (int i = 1; i < documents.length; i++) {
        if (set.contains(documents[i])) {
            return documents[i];
        }
        set.add(documents[i]);
    }
    return result;
}

时间复杂度O(n) 空间复杂度O(n)

解法二：二分查找

要避免使用O(n)的辅助空间。因为所有数字都在1_{n之间并且一定有重复项，如果大小在1}k范围的数字有重复项，那么大小在1_{k范围内的数字的个数一定大于k。设定一个基准值 k=n/2，遍历数组统计大小在1}k范围的内数字个数，每次遍历为n，使用二分查找使得总时间复杂度为 O(nlogn)，空间复杂度为 O(1)。

public int findRepeatDocument(int[] documents) {
    if (documents == null) {
        return -1;
    }
    int l = 1;
    int r = documents.length - 1;
    while (l <= r) {
        int m = ((r - l) >> 1) + l;
        int count = countInRange(documents, l, m);
        if (l == m) {
            if (count > 1) {
                return l;
            }
            else {
                return -1;
            }
        }
        if (count > (m - l + 1)) {
            r = m;
        }
        else {
            l = m + 1;
        }
    }
    return -1;
}

/**
 * 遍历数组
 */
private int countInRange(int[] documents, int start, int end) {
    int cnt = 0;
    for (int i = 0; i < documents.length; i++) {
        if (documents[i] >= start && documents[i] <= end) {
            cnt++;
        }
    }
    return cnt;
}