287 - Find the Duplicate Number

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.

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(n2).
4. There is only one duplicate number in the array, but it could be repeated more than once.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Hide Tags

Array Two Pointers Binary Search

Hide Similar Problems

(H) First Missing Positive (M) Single Number (M) Linked List Cycle II (M) Missing Number

好题。
刚开始完全木有思路，只好试着写了一个暴力的，果不其然耗时惊人。
后来忘了只读的限制，写了一个线性的，每次把到达当前元素的下标的相反数放入该位置，
这样重复访问的时候就会遇到所使用的下标的相反数，从而可以找到重复的元素。
虽然可以找到答案，耗时也不多，但违反了只读的要求。

要只读，还要线性，还要常量空间，实在是有难度。
提示里有双下标，二分查找。但数组是随机的，二分查找实在是想不出怎么做。
双下标通常有几种用法，一种是首尾收拢，例如2sum；另一种是新旧位置，例如数组去重；
还有一种，就是链表里的快慢指针。

逐个比划了一下，原来奥秘在于最后一种，快慢指针。
实际上重复的元素就好比是链表里圈的起点，当我们用它的值作为新的下标去访问的时候，就会“绕圈”了！
果然，按照这个思路，快慢下标，直到重合，说明有圈，
再让快的回到起点，快慢同步移动，重合的时候，就是答案了。

这个题目设计的精巧之处在于，
首先要利用数值的范围，他们的值不会超过个数-1，这就意味着，可以用这些值，充当下一步的索引，
于是逐步推进变成了走跳棋，（不知道这个是不是提示里的二分查找。。。）
然后跳棋实际上又被当成了链表，只不过不是用指针，而是用val当作新下标，也就相当于 next 指针，
从而利用链表里快慢指针的路子，最终既不改变数组内容，又不需要更多空间开销，还速度解决问题，
绝对的多快好省，相当精妙的设计！！

class Solution {
public:
    //at most O(2n) solution without modify the original array
    int findDuplicate(vector<int>& nums) {
        int sz=nums.size(), idx_slow=0, idx_fast=0, rst=0;
        if(sz)
        {
            do
            {
                idx_fast = nums[nums[idx_fast]];
                idx_slow = nums[idx_slow];
            }while(idx_fast<sz && idx_slow<sz && idx_slow!=idx_fast);

            idx_fast = 0;
            while(idx_fast<sz && idx_slow<sz && idx_slow!=idx_fast)
                idx_slow=nums[idx_slow], idx_fast=nums[idx_fast];

            rst = idx_fast;
        }
        return rst;
    }

    //quick, at least O(n), 20 ms, but modified the original array
    int findDuplicate1(vector<int>& nums) {
        int sz=nums.size(), idx=0, rst=0;
        if(sz)
        {
            while(nums[idx]!=0-idx)     //ends if met negative of idx
            {
                int tmp = nums[idx];
                nums[idx] = 0-idx;      //rewrite data as -idx
                idx = tmp;
            }
            rst = 0-nums[idx];
        }
        return rst;
    }
   
    //naive way, O(n^2), 1748 ms, terrible
    int findDuplicate0(vector<int>& nums) {
        int sz=nums.size();
        for(int ii=sz-1; ii>0; ii--)
            for(int jj=ii-1; jj>=0; jj--)
                if(nums[ii]==nums[jj])
                    return nums[ii];
        return 0;
    }
};
12 ms, 16 ms, 1748 ms.