287. Find the Duplicate Number 寻找重复数

[GH1995]

287. Find the Duplicate Number

Difficulty: Medium

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 1:

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

Example 2:

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

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

Solution

Language: C++

class Solution {
public:
    int findDuplicate(vector<int> &nums) {
      int left = 0, right = nums.size();
​
      while (left < right) {
        int mid = left + (right - left) / 2;
        int count = 0;
​
        for (auto &num : nums)
          if (num <= mid)
            ++count;
​
        if (count <= mid) // 加起来是合理的
          left = mid + 1;
        else
          right = mid; // 不用减一
      }
​
      return right;
    }
};

[GH1995]

只能考虑用二分搜索法了，我们在区间 [1, n] 中搜索，首先求出中点 mid，然后遍历整个数组，统计所有小于等于 mid 的数的个数，如果个数小于等于 mid，则说明重复值在 [mid+1, n] 之间，反之，重复值应在 [1, mid-1] 之间，然后依次类推，直到搜索完成，此时的 low 就是我们要求的重复值