分析
抽屉原理
然后我们采用分治的思想,将每个数的取值的区间[1, n]
划分成[1, n/2]
和[n/2+1, n]
两个子区间,然后分别统计两个区间中数的个数。
划分之后,左右两个区间里一定至少存在一个区间,区间中数的个数大于区间长度。
代码实现
class Solution
{
public:
int duplicateInArray(vector<int> &nums)
{
int l = 1, r = nums.size() - 1;
while (l < r)
{
int mid = l + r >> 1; // 划分的区间:[l, mid], [mid + 1, r]
int ans = 0; // 区间中数的个数
for (auto c : nums) ans += c >= l && c <= mid;
if (ans > mid - l + 1) r = mid;
else l = mid + 1;
}
return l;
}
};