我们把从1~n的数字从中间的数字m分为两部分,前面一半为1-m,后面一半是m+1-n,如果1-m的数字超过了m,那么这一半的区间内一定包含重复的数字;否则另外一半m+1-n的区间里面一定包含重复的数字。我们可以继续把重复数字的区间一分为二,直到找到一个重复的数字。这其实就是二分法的使用,只不过多了统计数字的步骤!!!代码如下(是正确的):
class Solution {
public:
int duplicateInArray(vector<int>& nums) {
int left = 1;
int right = nums.size() - 1;// 长度是n+1的数组
// left - right = 1-n
while(left < right)
{
int mid = left + (right - left) / 2;
int count = 0;
// 统计左半边的数字个数
for(int i = 0; i < nums.size(); i++)
{
if(nums[i] >= left && nums[i] <= mid)
{
count++;
}
}
// 左边的数字个数 大于区间长度 说明重复数字在左边
if(count > mid - left + 1)
{
right = mid;// 将right 指定为mid
}
else
{
// 重复数字在右半边
left = mid + 1;
}
}
return left;
}
};
嘿嘿