查阅更多的题解，请点击

Problem

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:

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

Solution

solution one

O(n) time, O(n) space

看到该题的直观想法，对n+1个数的数组进行遍厉，将每个数插入一个hash表，若插入时该元素已经在表中存在，则返回该元素，由题目要求，该元素一定存在。由于hash表的插入和查找都是O(1)，该算法最坏情况下需要遍历到数组尾，所以时间复杂度:O(n) 空间复杂度：O(n)。

solution two

O(nlogn) time, O(1) space

由于题目要求，空间开销要尽可能的小，所以需要不同于解法一的算法。由于输入数据结构为数组，考虑原问题是否可以reduce：一个很希望达成的reduce策略：将输入数据分成两组，一组中包含duplicate数据，一组不包含；这样，我们就将原问题reduce到了更小的问题，这样的策略很像广为人知的二分查找。但不同的该问题输入是无序数据，如何对数据进行我们所希望的划分？注意题目中的条件：

• 设任意一个数为a_k,有a_k\in [1,n]
• n+1个数，仅存在一组重复数据

则可以根据(n+1)/2对输入数据进行划分，即duplicate one是在[1,(n+1)/2]还是在区间((n+1)/2,n]

solution three

O(n) time,o(1) space

该解法非常的优雅，是在LeetCode的讨论区看到的，该方法很巧妙，但理解起来并不容易.

对于题目给出的n+1个数组，若n+1个数互不相同，则数组下标和该数本身有一一对应关系，比如数组{2,1,3},有下标和数值的对应关系：0->2,1->1,2->3，该对应关系类似函数的一一映射，设数组下标为x，对应值为f(x),如果我们从下标为0出发，根据这个函数计算出一个值，以这个值为新的下标，再用这个函数计算，以此类推，直到下标超界。实际上可以产生一个类似链表一样的序列,该例中下标的序列为0->2-3；若如题目所言，存在这样的重复项，则无法实现一一映射，序列中也会出现环，找到该环，就可以找到重复项。

int slow = 0;
int fast = 0;
while (true)
{
    slow = nums[slow];
    fast = nums[nums[fast]];
    if (slow == fast)
        break;
}

上述代码中通过快慢指针，尝试寻找环(即出现f(x_1)=x=f(x_2))，这里可能会引起疑惑，会不会我们找到属于f(x)=x的情况（姑且称之为自环）?不妨用反证法证明：

• 假设经过k步，出现f(x)=x的情况，上述查找过程会停止。由于我们在第k次，查找的数组下标为k，则可以说明在前k-1次中，出现数组下标为i(1!=x),f(x)=x。则停止时找到的，仍是我们希望找的的环。

GitHub传送门

solution one

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        unordered_set<int> set;
        int result = 0;
        for(auto num:nums){
            if(set.find(num)!=set.end()){
                result = num;
                break;
            }else{
                set.insert(num);
            }
                
        }
        return result;
    }
};

solution two

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

####solution three

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