287. Find the Duplicate Number 287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2]
Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

Note:

1. You must not modify the array (assume the array is read only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than O(n²).
4. There is only one duplicate number in the array, but it could be repeated more than once. 287. Find the Duplicate Number

---

一个长度为n+1的数组，包含1~n的数字，证明至少有一个数字重复，并找出这个重复数字。 证明好说，鸽巢原理。要求在线性时间复杂度和常数空间复杂度把这个重复的数字找出来就有难度了，而且不能修改原数组，难以用上LeetCode Find All Numbers Disappeared in an Array的技巧。 这题确实hard，看了看提示，以及网上的题解，现总结如下。 第一种解法是二分搜索。根据鸽巢原理，如果有n+1个[1,n]的数，则必有一个数重复了，把区间分成[1,m]和[m+1,n]，则重复的数字要么出现在[1,m]，要么出现在[m+1,n]，所以只需统计一下小于等于和大于m的数字的个数，数字多的那个区间肯定是存在重复数字的区间。然后在那个区间递归的找下去，直到找到重复数字。
完整代码如下：

class Solution {
public:
    int findDuplicate(vector<int>& nums)
    {
        int low = 1, high = nums.size() – 1;
        while (low < high) {
            int mid = (low + high) / 2, low_cnt = 0;
            for (int i = 0; i < nums.size(); ++i) {
                if (nums[i] <= mid)
                    ++low_cnt;
            }
            if (low_cnt > mid) {
                high = mid;
            }
            else {
                low = mid + 1;
            }
        }
        return low;
    }
};

本代码提交AC，用时9MS。
还有一种解法和LeetCode Linked List Cycle II很类似，如果存在重复数字，则使用下标递归访问的时候，会出现循环访问。首先通过快慢指针找到循环相遇点，然后慢指针回到原点，快慢指针按相同速度前进，直到遇到函数值相同时停止，这个相同的函数值即为重复数字。一些证明可以参考这个博客。
完整代码如下：

class Solution {
public:
    int findDuplicate(vector<int>& nums)
    {
        int slow = 0, fast = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast)
                break;
        }
        slow = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[fast];
            if (slow == fast)
                return slow;
        }
    }
};

本代码提交AC，用时13MS。

二刷。对二分搜索的解读。假设数组没有重复数字，比如[1,2,3,4,5,6,7]，则对于任意一个数x，<=x的数的个数和x是相等的，比如<=1的数有1个，<=2的数有2个etc…如果出现重复数字，假设比中点小，则<=m的数的个数要大于m。所以代码中每次比较是low_cnt和m比较。

l、r、while(l<=r)都是标准的二分搜索框架。最后返回r+1，想象一直low_cnt>m，知道不满足while循环，则最后一个满足的就是r+1。

class Solution {
public:
	int findDuplicate(vector<int>& nums) {
		int n = nums.size();
		int l = 1, r = n - 1;
		while (l <= r) {
			int m = l + (r - l) / 2;
			int low_cnt = 0;
			for (int i = 0; i < n; ++i) {
				if (nums[i] <= m)++low_cnt;
			}
			if (low_cnt > m)r = m - 1;
			else l = m + 1;
		}
		return r + 1;
	}
};