特殊排序

2023-12-17 22:50:06

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

题目大意

在这里插入图片描述

解题思路

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

文章来源:https://blog.csdn.net/m0_73865722/article/details/135051280
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。