AcWing 14. 不修改数组找出重复的数字
原题链接
简单
作者:
Jsweet
,
2022-02-25 15:38:46
,
所有人可见
,
阅读 159
参考了y总的代码,我是新手,大概的意思是找左边区间大于中间值的个数是否比右边多,如果多,那答案会在左边
否则就在右边,层层的分,最后确定答案,类似于二分查找
其次我觉得1000的范围,哈希或者桶排序也可以暴出来,只不过没写
class Solution {
public:
int duplicateInArray(vector<int>& nums) {
int l = 1, r = nums.size() - 1;
while (l < r)
{
int s = 0;
int mid = l + r >> 1;//二分跟抽屉原理,1 到 n 的区间有n + 1个数,那肯定是有重复
//其次每次划分区间,一定会有个区间的数大于中间值的个数比另一个多
//最后为一时就代表找到了答案
cout << "原来的区间" << l << ' ' << r << ' ' << mid << endl;
for(auto a : nums)
{
cout << a << ' ';
s += a >= l && a <= mid;
}
cout << endl << "个数" << s << endl;
if(s > mid - l + 1) r = mid;
else l = mid + 1;
cout << "二分后的区间" << l << ' ' << r << ' ' << mid << endl;
}
return r;
}
};