LeetCode 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.

解析：一个数组包含n+1个元素，每个元素的取值在[1,n]之间，只有一个元素有重复，找到这个元素。要求：不能更改原数组，不能使用额外的空间。时间复杂度需要小于\(O(n^2)\)。

此题目类似于将10个鸡蛋放进9个抽屉里面，肯定有一个抽屉是2个鸡蛋的，这里重复的次数可能多个。

思路1：

根据限制条件，没法使用HashMap之类的结构，考虑二分查找，low=1,high=n，然后找到中间元素mid，计算数组中小于等于mid的数量cnt。如果cnt<=mid，则说明重复元素在右侧，否则在左侧。代码如下：

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int low = 1, high = nums.size()-1;
        while(low < high)
        {
            int mid = (low + high) / 2;
            int cnt = 0;
            for(auto num: nums)
            {
                if(num <= mid)
                    cnt++;
            }
            if(cnt <= mid)
                low = mid +1;
            else
                high = mid;
        }
        return low;
    }
};

思路2：看到网上的另一种解法，借鉴判断链表是否存在环并找到入口的思路。重复元素即为链表的环，采用快慢指针，慢指针每次走一步，快指针每次走两步。如果相遇则存在环。这时一个指针从链表头，一个指针从相遇点出发，每次走一步，相遇时即为环的入口点。

具体分析参见 https://xianpengcui.com/2019/10/06/leetcode-142-linked-list-cycle-ii/

代码如下：

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        if(nums.size() > 1)
        {
            int slow = nums[0];
            int fast = nums[nums[0]];
            while(fast != slow)
            {
                slow = nums[slow];
                fast = nums[nums[fast]];
            }
            fast = 0;
            while(fast != slow)
            {
                slow = nums[slow];
                fast = nums[fast];
            }
            return slow;
        }
        return -1;
    }
};

参考：

https://leetcode.com/problems/find-the-duplicate-number/discuss/72846/My-easy-understood-solution-with-O(n)-time-and-O(1)-space-without-modifying-the-array.-With-clear-explanation.

https://www.cnblogs.com/grandyang/p/4843654.html