LC287.寻找重复数

原题链接：https://leetcode.cn/problems/find-the-duplicate-number/

给定一个包含 个整数的数组 ，其数字都在 范围内（包括 和 ），可知至少存在一个重复的整数。 假设 只有 一个重复的整数 ，返回 这个重复的数 。 你设计的解决方案必须 不修改 数组 且只用常量级 #card=math&code=O%281%29&id=bfPpj) 的额外空间。

示例 1：

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

示例 2：

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

• 提示：
• 
• 
• 
• 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
• 进阶：
• 如何证明 中至少存在一个重复的数字?

• 你可以设计一个线性级时间复杂度 #card=math&code=O%28n%29&id=QGBAv) 的解决方案吗？

  思路1：二分查找

• 抽屉原理：5个抽屉放6个球，至少有一个抽屉中球的数量 >= 2;

• 如果n个位置放n个数字，排序之后，如果希望涨幅尽量大，那么序列就是[1,2,3,4,...,n]
  • 现在插入1个数字x进去，无论的数字x是多少，数组都被分成了两段[1,2,3...x-1]``[x...,n]
  • 那么数组的右半部分[x...n]全部被“往后顶了一格”，因此，对于右边部分中任意下标k而言：nums[k] < k + 1
  • 所以，x相当于满足条件的“右半部分”数组的左端点。二分查找即可找到。
• 以上的例子是说明了涨幅最快的情况，其他情况比这个情况宽松，因此更加能找到。

代码1：

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < mid + 1) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return nums[left];
    }
};

思路2：快慢指针

思路3：Floyd判圈法

思路4：位运算