题目描述
通过交互的方式得知任意一对元素的偏序关系
样例
输入
[[0, 1, 0], [0, 0, 0], [1, 1, 0]]
输出
[3, 1, 2]
算法1
(归并排序) $O(nlog{n})$
观察数据范围,元素最多1000个,最多允许10000次,这正好是$O(nlog{n})$允许的时间复杂度范围,只需要把
快排(用快排会MLE不知道为啥)或者归并排序等复杂度为$O(nlog{n})$的排序算法(排序算法的下界)的比较两个元素的部分替换成交互
函数即可.
时间复杂度
归并排序先分治再合并,每次2分然后合并$O(n)$,合计$O(nlog{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:
void quick_sort(vector<int>& a, int l, int r){
if(l >= r) return ;
// int i = l - 1, j = r + 1, x = a[rand() % (r - l) + l];
int i = l - 1, j = r + 1, x = a[l];
while(i < j){
do i++; while(compare(a[i], x));
do j--; while(!compare(a[j], x));
if(i < j) swap(a[i], a[j]);
}
quick_sort(a, l, j);
quick_sort(a, j+1, r);
}
void merge_sort(vector<int>& a, int l, int r){
if(l >= r) return;
int m = (l + r) >> 1;
merge_sort(a, l, m);
merge_sort(a, m + 1, r);
int i = l, j = m + 1, k = 0;
vector<int> t( r - l + 1);
while(i <= m and j <= r){
if(compare(a[i], a[j])) t[k++] = a[i++];
else t[k++] = a[j++];
}
while(i <= m) t[k++] = a[i++];
while(j <= r) t[k++] = a[j++];
for(int i = l; i <= r; ++i) a[i] = t[i - l];
}
vector<int> specialSort(int n) {
vector<int> re(n);
for(int i = 0; i < n; ++i) re[i] = i + 1;
// quick_sort(re, 0, n-1);
merge_sort(re, 0, n-1);
return re;
}
};