面试题 3：数组中重复的数字.md

试题链接：数组中重复的数字_牛客题霸_牛客网

方法一：哈希表

• 思路：哈希表计数。
• 时间复杂度：O(n)
• 空间复杂度：O(n)

#include <vector>
class Solution {
public:
    int duplicate(vector<int>& numbers) {
        int n = numbers.size();
        vector<bool> isdup(n);

        for (int num : numbers) {
            if (isdup[num]) {
                return num;
            }
            isdup[num] = true;
        }

        return -1;
    }
};

方法二：交换法

• 思路：因为数组长度为 n，且内容为 0 ~ n - 1 的数字，所以当没有出现重复数字的时候，排序后下标 i 对应的数字就是 i，因此可以遍历数组，当下标 i 对应的数字 j 不等于 i 时，就将其与下标 j 对应的位置交换，如果下标 j 位置的数字已经存放 j 了，则说明存在重复数字 j。
• 时间复杂度：O(n)
• 空间复杂度：O(1)

#include <vector>
class Solution {
public:
    int duplicate(vector<int>& numbers) {
        int n = numbers.size();
        
        for (int i = 0; i < n; i++) {
            while (numbers[i] != i) {
                int j = numbers[i];
                if (numbers[j] == j) {
                    return j;
                }

                swap(numbers[i], numbers[j]);
            }
        }

        return -1;
    }
};

另一种变体：不修改数组找出重复的数字

试题链接：14. 不修改数组找出重复的数字 - AcWing题库

• 思路：不能采用上述方法来交换数组元素的位置，使用哈希表是可以的，但是如果要实现 O(1) 的空间复杂度可以使用二分的方法。由于数组长度为 n + 1，且数字范围为 1 ~ n，故一定存在一个重复的数字。我们可以二分这个数字范围，将 1 ~ n 划分为 1 ~ m 和 m + 1 ~ n ，然后计数数组中数字在 1 ~ m 范围的数字个数，如果数字个数大于区间长度则说明这个区间类存在重复数字，由于题目至少存在一个重复数字，因此左右两个区间一定至少有一个是满足条件的，以此类推，直到区间长度为 1 时则找到了重复的数字。但是这个方法只能找到一个重复的数字，不能找到全部重复的数字，因此需要根据题目要求来选择使用的方法。
• 时间复杂度：O(nlogn)
• 空间复杂度：O(1)

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int n = nums.size() - 1;
        
        int l = 1, r = n;
        while (l < r) {
            int m = l + r >> 1;
            if (countRange(nums, l, m) > (m - l + 1)) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        
        return l;
        
    }
    
    int countRange(vector<int>& nums, int l, int m) {
        int count = 0;
        for (int num : nums) {
            if (num >= l && num <= m) {
                count++;
            }
        }
        return count;
    }
};