二分模板-1
while(l<r){
mid = l+r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
此题y总视频给的是模板-2的做法,最后二分得到的结果是待插位置的前一个位置,个人感觉略绕,不太直接(当然每个人习惯不同hhh)
这里贴一份利用y总二分模板-1来做的思路以及代码。
思路
整体思路是对于每一个数$i$,先在已排好序的数组中二分找出待插位置$r$,然后把包括$r$位置之后的所有元素往后移动一位,最后把新的数放到位置$r$。
二分的条件是compare(nums[mid], i),当mid位置的元素严格小于新数$i$时返回true。
接下来结合题目场景来分析使用哪个模板:
要特别考虑边界的情况,也就是如果mid刚好就是答案的情况。此时$i$的插入位置应该在mid的右边(因为$i > nums[mid]$),所以接下来这一行写成 l = mid + 1 比较好!然后发现这是模板-1(和模板等价,只是正负倒过来而已),那else语句就应该写成 r = mid 。
这么写的话,在一开始有边界的取值应该是nums.size(),因为有可能插到最后一个位置。
这样最后不需要特判nums[r]和nums[r+1]。
// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.
class Solution {
public:
vector<int> specialSort(int N) {
vector<int> nums;
for(int i = 1; i<=N; i++){
int mid, l = 0, r = nums.size();
while(l<r){
mid = l+r>>1;
if(compare(nums[mid], i)) l = mid + 1;
else r = mid;
}
nums.push_back(i);
int j;
for(j = nums.size()-2; j>=r; j--){
swap(nums[j], nums[j+1]);
}
}
return nums;
}
};
边界处理说得挺有道理的
谢谢~