AcWing 113. 特殊排序
原题链接
简单
作者:
牛奶小柒Luke
,
2021-01-18 16:55:28
,
所有人可见
,
阅读 320
// 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> res;
res.push_back(1);
for(int i = 2;i <= n;++i){
int l = 0,r = res.size() - 1;
while(l < r){
int mid = l + r + 1 >> 1;
if(compare(res[mid],i)) l = mid;
else r = mid - 1;
}
res.push_back(i);
for(int j = res.size() - 2;j > r;--j){
swap(res[j],res[j + 1]);
}
if(!compare(res[r],i)) swap(res[r],res[r + 1]);
}
return res;
}
};