特殊排序

title: 特殊排序
date: 2023-12-17 21:32:01
tags: 二分
categories:

题目大意

解题思路

交互：不知道大小关系，只能通过调用compare接口询问
根据数学归纳法，假设前 $k?1$ 个元素已经按要求排成一行，如果能确定第 $k$ 个元素应该放在哪一个前面，即可解决该问题
通过二分确定这个位置。若第 $k$ 个元素比第 $mid$ 个元素小，令 $r=mid$,否则 $l=mid+1$。

时间复杂度

不超过 NlogN

实现代码

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;
                if(compare(res[mid],i)) l = mid + 1;
                else    r = mid - 1;
            }
            res.push_back(i);
            for(int j = res.size() - 2;j > r;j--)   swap(res[j],res[j + 1]);
        }
        return res;
    }
};