287. Find the Duplicate Number

problem description

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:

You must not modify the array (assume the array is read only). You must use only constant, O(1) extra space. Your runtime complexity should be less than O(n2). There is only one duplicate number in the array, but it could be repeated more than once.

algorithm thought

这题看着很简单，不就是找个重复的数字嘛。但是下面的note给出了很多限制。首先不能修改数组，然后要保证空间复杂度是O(1)。也就是不能用map和set这种数据结构辅助解题了。

这里题目给出的限制是数组中的值的范围是1-n，数组有n+1个数。数组的下标范围是0-n。也就是说，如果将数组中的值看做下标，就可以将数组看成一个链表。重复的值，意思就是链表中有环。

转换题目之后，就可以利用链表判圈问题解题了。直接使用快慢指针即可

code

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

        while(slow!=fast){
            slow=nums[slow];
            fast=nums[nums[fast]];
        }


        slow=0;
        while(slow!=fast){
            slow=nums[slow];
            fast=nums[fast];
        }

        return slow;
    }
};

algorithm analysis

空间复杂度O(1)，时间复杂度O（n）