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：

Input: [1,3,4,2,2]
Output: 2

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.

解释下题目：

在一个长度为n+1的数组中，放入了n个范围在[1,n]的数字（就算每个数字都出现一次也放不满，所以肯定至少有一个数字出现了至少两次），然后保证最多有一个数字出现了多次，求出这个数字。

1. 错误的方法

实际耗时：错误

public int findDuplicate(int[] nums) {
    if (nums.length < 2) {
        return -1;
    }
    int realSum = 0;
    for (int i : nums) {
        realSum += i;
    }
    int sum = (nums.length) * (nums.length - 1) / 2;
    return nums[0] == nums[1] ? nums[0] : realSum - sum;
}

  思路我一开始以为是1-n所有的数字都会出现，那就用高斯求和求一下，然后两个互相减一下就得出了那个数字，然而实际情况不是这样的......，因为可能会出现{1,2,2,2,2,3,5}这种情况。

时间复杂度O(n)

空间复杂度O(1)

2. 类似天平称假金子的题目

实际耗时：3ms

public int findDuplicate(int[] nums) {
    int left = 0, right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        int count = 0;
        for (int num : nums) {
            if (num <= mid) {
                count++;
            }
        }
        if (count <= mid) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return right;
}

  思路就是跟以前的奥数用天平称假的金子的类似，只不过在这里就有点类似二分法的味道

时间复杂度O(nlogn)

空间复杂度O(1)

3. 类似循环链表的感觉

实际耗时：0ms

public int findDuplicate(int[] nums) {
    int slow = 0, fast = 0;
    int slow2 = 0;
    while (true) {
        slow = nums[slow];
        fast = nums[nums[fast]];
        if (slow == fast) {
            break;
        }
    }
    while (true) {
        slow = nums[slow];
        slow2 = nums[slow2];
        if (slow == slow2) {
            break;
        }
    }
    return slow;
}

  思路第一个循环用来找到循环链表中循环的部分，第二个循环用来找到循环的开头的部分（也就是答案）

时间复杂度O(n)

空间复杂度O(1)