题目描述
有N个元素,编号1.2..N,每一对元素之间的大小关系是确定的,关系具有反对称性,但不具有传递性。
注意:不存在两个元素大小相等的情况。
也就是说,元素的大小关系是N个点与N*(N-1)/2条有向边构成的任意有向图。
然而,这是一道交互式试题,这些关系不能一次性得知,你必须通过不超过10000次提问来获取信息,每次提问只能了解某两个元素之间的关系。
现在请你把这N个元素排成一行,使得每个元素都小于右边与它相邻的元素。
你可以通过我们预设的bool函数compare来获得两个元素之间的大小关系。
例如,编号为a和b的两个元素,如果元素a小于元素b,则compare(a,b)返回true,否则返回false。
将N个元素排好序后,把他们的编号以数组的形式输出,如果答案不唯一,则输出任意一个均可。
算法:二分
时间复杂度:$O(N^2·log(N))$
C++代码
// 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(1,1);
for(int i=2;i<=N;i++){
//找到小于等于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);
//将最末尾的结果交换到r+1
for(int j=res.size()-2;j>r;j--)swap(res[j],res[j+1]);
if(compare(i,res[r]))swap(res[r],res[r+1]);
}
return res;
}
};