LeetCode 热题 100_寻找重复数（100_287_中等_C++）（技巧）(暴力解法；哈希集合；二分查找)

题目描述：

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

输入输出样例：

示例 1：
输入：nums = [1,3,4,2,2]
输出：2

示例 2：
输入：nums = [3,1,3,4,2]
输出：3

示例 3：
输入：nums = [3,3,3,3,3]
输出：3

提示：
1 <= n <= 10⁴
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次

题解：

解题思路：

思路一（暴力解法）：

1、双重循环，进行枚举。

2、复杂度分析：
① 时间复杂度：O(n²)，n 代表数组中元素的个数，使用了双重循环。
② 空间复杂度：空间复杂度是 O(1)。

思路二（哈希集合）：

1、使用哈希集合来存储每个数字，若当前元素之前已经存在一个相同的值在哈希集合中，则当前元素为重复元素。

2、复杂度分析
① 时间复杂度：O(n)，n 代表数组中元素的个数，遍历一遍数组。
② 空间复杂度：O(n)，n 代表数组中元素的个数，使用哈希集合来存储元素。

思路三（二分查找）：

1、已知数字的范围为 [1 , n ] ,总共有 n + 1 个整数 且 nums 只有 一个重复的整数。则肯定存在 [1,2,…,n] 其中一个元素重复，则可采用二分查找。

• 假设有三个物品放两个抽屉那么必定有一个抽屉有两个物品
• 运用这个原理我们可以运用到此问题，若nums={1,3,4,2,2} 。n=4
• 假设我们统计 小于等于 2 元素的个数等于 3，3 个数放 1，2 两个位置必定有一个重复元素
• 那重复元素一定是 1 或者 2，那我们再查看 小于等于 1 元素的个数等于 1 则正好不重复，则重复元素必定是 2 。

2、复杂度分析
① 时间复杂度：O(nlogn)，其中 n 为 nums 数组的长度，采用了二分查找。

② 空间复杂度：O(1)。

代码实现

代码实现（思路一（暴力解法））：

class Solution1 {
public:
    // 定义函数 findDuplicate，接收一个整数数组 nums，返回数组中第一个重复的元素
    int findDuplicate(vector<int> &nums) {
        // 外层循环：遍历数组 nums 中的每个元素
        for (int l = 0; l < nums.size(); l++) {
            // 内层循环：从当前元素的下一个位置开始遍历
            // 目的是比较 nums[l] 与 nums[r] 是否相等
            for (int r = l + 1; r < nums.size(); r++) {
                // 如果找到重复的元素，返回该元素
                if (nums[l] == nums[r]) {
                    return nums[l];  // 返回第一个重复的元素
                }
            }
        }
        
        // 如果没有找到重复元素，返回 0
        return -1;
    }
};

代码实现（思路二（哈希集合））：

class Solution2 {
public:
    // 定义函数 findDuplicate，接收一个整数数组 nums，返回数组中第一个重复的元素
    int findDuplicate(vector<int> &nums) {
        unordered_set<int> mp_set;
        for(auto &i:nums){
            if (mp_set.count(i)){
                return i;
            }
            mp_set.insert(i);
        }
        return -1;
    }
};

代码实现（思路三（二分查找））：

class Solution3 {
public:
    // findDuplicate 函数：用来查找给定数组中的重复数字
    int findDuplicate(vector<int> &nums) {
        int len = nums.size();  // 获取数组的长度

        int left = 1;  // 左指针设为 1，因为数组元素范围从 1 到 n
        int right = nums.size() - 1;  // 右指针设为 n-1，因为数组索引从 0 开始，元素值最大为 n

        // 使用二分查找的思想，判断重复数字的位置
        while (left < right) {
            // 计算中间值
            int mid = (left + right) / 2;

            // 统计数组中小于等于 mid 的元素个数
            int count = 0;
            for (auto &i : nums) {
                if (i <= mid) {
                    count++;  // 如果元素小于等于 mid，就增加计数
                }
            }

            // 如果小于等于 mid 的元素个数大于 mid，则说明重复的数字在左半部分
            if (count > mid) {
                right = mid;  // 将右指针移到 mid，继续在左半部分查找
            } else {
                left = mid + 1;  // 否则，重复的数字在右半部分，将左指针移到 mid + 1
            }
        }

        // 当 left == right 时，找到重复的数字
        return left;
    }
};

以思路二为例进行调试

#include<iostream>
#include<vector>
#include<unordered_set>
using namespace std;

class Solution2 {
public:
    // 定义函数 findDuplicate，接收一个整数数组 nums，返回数组中第一个重复的元素
    int findDuplicate(vector<int> &nums) {
        unordered_set<int> mp_set;
        for(auto &i:nums){
            if (mp_set.count(i)){
                return i;
            }
            mp_set.insert(i);
        }
        return -1;
    }
};

int main(int argc, char const *argv[])
{
    vector<int> nums={3,1,3,4,2};
    Solution2 s;
    cout<<s.findDuplicate(nums);
    return 0;
}

LeetCode 热题 100_寻找重复数（100_287)原题链接
欢迎大家和我沟通交流(✿◠‿◠)