[Leetcode 287] Find the Duplicate Number

作者 Shilei Tian 日期 2016-10-16
[Leetcode 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:

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

题目解读

题目的要求很简单,给定一个数组,大小为 n + 1,但实际上它只包含了 1nn 个数字,按照鸽巢原理,那么势必会有重复的元素,而本题也告诉大家,只有一个重复的数字,只不过重复的次数可能不止一次。给定的数组并没有顺序,而本题要求也不允许修改数组,这样就断了那个排序数组的念头了(但偷偷的告诉大家,这道题排序后遍历这样做依然可以 AC),空间复杂度的要求是 O(1),那么用哈希来做也不行。时间复杂度也告诉了。

解题思路

本题的解题思路,或者说是解题的小技巧就暗藏在它给的条件里面。试想,给定一个数 m,那么如果比 m 小的元素都没有重复的,那么整个序列里面小于等于 m 元素的个数应该恰好为 m;如果我们发现,比 m 小的元素大于 m 个,那么很显然,重复的数字在 1m 之间。这个套路是不是很熟悉?对,可以利用二分搜索来做。所以就有了我们下面的方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int low(1), high(nums.size() - 1), mid(0);
while (low < high) {
mid = low + (high - low) / 2;
auto cnt(0);
for (auto i = 0; i < nums.size(); ++i) {
if (nums[i] <= mid) {
++cnt;
}
}
if (cnt > mid) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
};

我们初始化低位是 1,高位是 n,然后进行二分搜索,这样最终退出循环后低位那个值实际上就是要求的结果。