AcWing 113. 特殊排序 - AcWing

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 113. 特殊排序原题链接简单

作者：

acwing_987 , 2019-03-10 14:04:32 , 所有人可见 , 阅读 8570

86

23

本题满足归并排序的要求（即使元素大小关系不具传递性）

可以用std::stable_sort实现

code:

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int>v;
        for(int i=1;i<=N;++i)v.push_back(i);
        stable_sort(v.begin(),v.end(),compare);
        return v;
    }
};

46 评论

DracoMalfoy 2022-04-28 21:00

回复

请问这题题意是啥啊

DracoMalfoy 2022-04-28 21:00

回复

枯了

Bingxiu 2023-05-05 18:26

回复

说实话，这个还是有点bug，即使用普通stl快排也能过，由python获取到计算询问次数的是Num，存输入数组的是num，所以有两种策略
第一种：直接使用num数组，询问次数0
第二种：每次compare时将Num归零
我使用了第二种
代码：

// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

#include<numeric>
inline bool cmp(const int &a,const int &b){return Num=0,compare(a,b);}
class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> a;
        return a.resize(N),std::iota(a.begin(),a.end(),1),random_shuffle(a.begin(),a.end()),sort(a.begin(),a.end(),cmp),a;
    }
};

jeffstart 2023-10-24 17:02

回复

tql

Youngforyou 2023-08-27 10:04

回复

有佬能解释一下题意吗？不理解啊

懵逼自动机 2023-06-02 21:46

回复

666

dancin 2023-03-17 18:26

回复

666

krio 2023-02-15 19:56

回复

有没有佬解释下归并排序的要求（即使元素大小关系不具传递性）

彩虹小马 2023-04-12 11:18

回复

通常情况下，元素的大小关系应该具有传递性，即如果a < b，b < c，那么a < c。但是，在归并排序中，如果元素大小关系具有传递性，就不能保证归并排序的稳定性。

归并排序的稳定性指的是，如果序列中有两个元素a和b，它们的值相等，但是在原序列中a出现在b的前面，那么在排序后的序列中，a仍然应该出现在b的前面。如果元素大小关系具有传递性，那么在合并两个有序序列的过程中，如果出现了大小相等的元素，那么它们的相对位置可能会发生变化，从而破坏了归并排序的稳定性。

因此，为了保证归并排序的稳定性，需要要求元素大小关系不具有传递性。这通常是通过在比较两个元素的大小时，如果它们的值相等，则将左边的元素视为小于右边的元素来实现的。这样做可以保证相等元素的相对位置不会改变。

悲伤哥 2023-07-08 17:41 回复了彩虹小马的评论

回复

阿拉伯数字之间的排序也是有传递性的啊，那按你这么说用归并排序去排序数字的话就没有稳定性了吗？

ahahahah 2023-02-15 10:55

回复

66666

Alitaa 2023-02-14 23:36

回复

66666

Hwretcheds 2022-08-08 19:09

回复

现在不行了

RwChen 2023-01-05 21:42

回复

还是可以ac啊

嘉然我好想当你的狗啊 2022-02-26 11:59

回复

666

xiaoxiaopy 2022-02-07 17:29

回复

666

jkloveg 2022-01-28 18:03

回复

nt

白生也 2022-01-26 23:02

回复

Orz%%%

ᔠዂϤ 2022-01-22 16:10

回复

nb

MOTSA 2022-01-01 01:26

回复

三连了，这次一定！

xc666 2021-12-06 17:13

回复

$nb$

雨天的尾巴 2021-11-14 22:06

回复

666666

杨大鑫_ωﾉ 2021-10-28 23:34

回复

66666666

jerryc06 2021-10-10 14:54

回复

666

也. 2021-09-15 21:53

回复

！这也太行了