AcWing 113. 特殊排序
原题链接
简单
作者:
乡村守望者
,
2020-02-17 14:21:40
,
所有人可见
,
阅读 781
// 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> ans(1,1);
for(int i=2;i<=N;++i){
int l = 0,r = ans.size()-1;
while(l<r)
{
int mid = l+r+1>>1;
//注意是和 ans里面的数比的
//
if(compare(ans[mid],i))l=mid;
else r = mid-1;
}
ans.push_back(i);
for(int j=ans.size()-2;j>r;j--)swap(ans[j],ans[j+1]);
//只有当r==0且ans[0]也比i大
if(r==0&&compare(i,ans[0])){
swap(ans[0],ans[1]);
}
}
return ans;
}
};
%%