【Leetcode】287. Find the Duplicate Number

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.

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.

Solution

public int findDuplicate(int[] nums) {
        int min = 0;
        int max = nums.length - 1;
        while (min <= max) {
            int mid = min + (max - min) / 2;
            int cnt = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] <= mid) {
                    cnt++;
                }
            }
            if (cnt > mid) {
                max = mid - 1;
            } else {
                min = mid + 1;
            }
        }
        return min;
    }

Result

Analyse

这里用了二分查找，复杂度是O(nlgn)，注意这里普通意义上的二分，普通二分查找默认数组肯定是有序的，这样可以进行二分查找，而这里已经注明了数组只读，但是根据存储的数据特点，一共n + 1个数字，存储了1 到n的数。根据抽屉原理，如果n + 1个东西放入n个抽屉，肯定有一个抽屉会存放超过一个东西。那这种情况下的二分，就不是index所在的值二分，而是index二分，那index肯定是有序的，所以可以进行二分查找。

Optimization

public int findDuplicate(int[] nums) {
        /*
        循环映射法则,如果是nums {2, 1, 3, 1}
        循环映射法则
        0 -> 2 1 -> 1 2 -> 3 3 -> 1
        即是 0 -> 2, {1, 3} -> 1, 2 -> 3
        有如下映射关系
        0 -> 2 -> 3 -> 1 -> 1 -> 1 -> 1
         */
        int slow = 0;
        int fast = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        int find = 0;
        while (find != slow) {
            find = nums[find];
            slow = nums[slow];
        }
        return find;
    }

Analyse

这个就和查找链表的环是一个性质，那么重点来了，为什么find从0开始跑，和slow跑汇合的点是环的起点。
我们可以这么想，如果只有一个环，一个走两步，一个走1步，就是跑圈的问题，当套圈的时候肯定是快的比慢的多跑了一圈。而两者速度相差一个单位，所以相遇肯定是在出发点。
那么回归这道题，如果是一个路径后面接了一个环，你想在走这段路径的时候，快慢相差了1，他们到达环的时间不同，所以在环里碰到的地点肯定不是环的起点，快的不仅速度快，而且出发还早，那么本来套圈的地方，还比慢的多走了路径的长度。
这样通过slow重新走，first开始走，他们速度相同，这样他们会合的时候肯定是在环的起点。