很多问题或者子问题本身带有一定的单调性, 当遇到单调性的时候, 利用二分搜索的思想去解决问题.
287.寻找重复数
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。示例 1：输入：nums = [1,3,4,2,2] 输出：2
示例 2：输入：nums = [3,1,3,4,2] 输出：3
分析:
1.可以用类似计数排序的思路, 用 cnt[i] 统计小于等于 i 的数字有多少个, 假设我们要找的重复的数字是 target, 那么 [1, target] 这部分数字里面所有的数都满足 cnt[i] <= i, 后半段数字 [target, n] 里面所有的数字都满足 cnt[i] > i; 直觉上理解, 在不重复的区间里面, 累计计数的结果不可能超过数字累计的结果; 但因为重复元素的存在, 可以让累计计数的结果反超当前的数字值 i; 举个例子:
nums 1 2 3 4
cnt 1 3 4 5
2.cnt[i] 随着 i 增大 cnt[i] 是单调的, 所以我们用二分查找
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int len = nums.size();
int l = 1;
int h = len;
int ans = -1;
while (l <= h) {
int mid = l + (h - l) / 2;
// 求出来 mid 之前的计数结果
int cnt = 0;
for (int i = 0; i < len; ++i) {
if (nums[i] <= mid) {
++cnt;
}
}
// mid >= cnt 说明重复数在左半边区间
if (cnt <= mid) {
l = mid + 1;
// 重复数如果在右半边区间
} else if (cnt > mid) {
h = mid - 1;
ans = mid;
}
}
return ans;
}
};
转载请注明来源, from goldandrabbit.github.io
