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.

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.

解法1：O(NlogN)

这题是一个binary search的变形。题目给的条件显示能套用的常用算法应该只剩下binary search了。
难点是怎么舍弃一半的空间。这里巧妙的用了这个特性：1 - n的数字的mid是（1+n)/2, 那么如果比mid小的数较多，说明重复的数在小半区。这样我们可以缩小范围。
如果比mid小的数较少，那么重复的数就在大半区。
计算出一个mid之后统计和mid大小的时候要遍历。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public int findDuplicate(int[] nums) {
        int left = 1, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // loop through nums
            int cnt = 0;
            for (int num : nums) {
                if (num <= mid) {
                    cnt++;
                }
            }
            if (cnt > mid) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

解法2：O(N)

龟兔赛跑的算法，和找闭环的入口的思路一样。这里用的是一个扩展了的算法。
核心就是对于slow指针apply function一次，而对于fast指针apply function两次。
具体的解释可以参考这个
Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0, fast = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) {
                break;
            }
        }
        fast = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[fast];
            if (slow == fast) {
                break;
            }
        }
        return slow;
    }
}