acwing113. 特殊排序

题目来源

acwing

题目难度

2星

算法标签

二分

参考程序

// 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); //(a, b)初始化a个b
        for(int i = 2; i <= N; i ++)
        {
            int n = ans.size();
            int l = 0, r = n-1;
            while(l < r)
            {
                //找到可以插入位置的前一个数
                int mid = (l+r+1)/2;
                if(compare(i, ans[mid])) // i < ans[mid]
                {
                    //左半边一定有解，右半边不一定
                    r = mid-1;
                }
                else
                {
                    //右半边一定有解, 左半边不一定
                    l = mid;
                }
            }
            //对于l==r==0还需要重新判断一下是不
            //是指针无奈才留在这里，实际要再往左
            if(l == 0 && compare(i, ans[0])) //i < ans[i]
            {
                l --;
            }
            ans.push_back(i);
            //这里n-1是倒数第二个数
            for(int k = n-1; k > l; k --) 
            {
                swap(ans[k+1], ans[k]);
            }
        }
        return ans;
    }
};