快慢指针

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.

• 不能modify array, swap方法不能用了
• O(1) hashmap不能用了
• 由于O(n^2) 暴力法不能用

假设数组中没有重复，那我们可以做到这么一点，就是将数组的下标和1到n每一个数一对一的映射起来。比如数组是213,则映射关系为0->2, 1->1, 2->3.

但如果有重复的话，这中间就会产生多对一的映射，比如数组2131,则映射关系为0->2, {1，3}->1, 2->3。这样，我们推演的序列就一定会有环路了，这里下标的序列是0->2->3->1->1->1->1->...，而环的起点就是重复的数。

所以该题实际上就是找环路起点的题，和Linked List Cycle II一样。我们先用快慢两个下标都从0开始，快下标每轮映射两次，慢下标每轮映射一次，直到两个下标再次相同。这时候保持慢下标位置不变，再用一个新的下标从0开始，这两个下标都继续每轮映射一次，当这两个下标相遇时，就是环的起点，也就是重复的数。对这个找环起点算法不懂的，请参考Floyd's Algorithm。

注意 ：第一次找快慢指针相遇用do-while循环。

//O(n)
public class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;

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

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

        return find;
    }
}

这一题还有一种binary search的做法，利用的是pigeon hole原理： 如果前n/2个数，出现的次数大于n/2，那么重复一定是在前 n/2.

O(nlogn)
public class Solution {
    public int findDuplicate(int[] nums) {
        // pigeon hole
        int min = 0;
        int max = nums.length - 1;

        while(min <= max) {
            int mid = (min + max) / 2;

            int count = 0;
            for(int i = 0; i < nums.length; i++) {
                if(nums[i] <= mid) {
                    count++;
                }
            }

            if(count > mid) {
                max = mid - 1;
            } else {
                min = mid + 1;
            }
        }
        return min;
    }
}