题目描述

有N个元素，编号1.2..N，每一对元素之间的大小关系是确定的，关系不具有传递性。

也就是说，元素的大小关系是N个点与N*(N-1)/2条有向边构成的任意有向图。

然而，这是一道交互式试题，这些关系不能一次性得知，你必须通过不超过10000次提问来获取信息，每次提问只能了解某两个元素之间的关系。

现在请你把这N个元素排成一行，使得每个元素都小于右边与它相邻的元素。

你可以通过我们预设的bool函数compare来获得两个元素之间的大小关系。

例如，编号为a和b的两个元素，如果元素a小于元素b,则compare（a,b）返回true，否则返回false。

将N个元素排好序后，把他们的编号以数组的形式输出，如果答案不唯一，则输出任意一个均可。

数据范围

$N < 1000$

样例

[[0, 1, 0], [0, 0, 0], [1, 1, 0]]

输出样例

[3, 1, 2]

注意

不存在两个元素大小相等的情况。

归并排序

$O(nlgn)$

看题目的时候直觉是merge sort, 试了一下意外的过了.

这里如果比较大小的函数起名不叫做compare而是compareab(int a, int b)的话, 应该可以再省些行数, 在comparator里面直接调用.

Java 代码

// The compare API is defined in the parent class Relation:
//      boolean compare(int a, int b);
//      return boolean means whether a is less than b.

class Solution extends Relation {
    public int[] specialSort(int N) {
        // merge sort?
        int[] re = new int[N];
        for(int i = 0; i < N; i++) re[i] = i + 1;
        mergesort(re, 0, N - 1);
        return re;
    }

    void mergesort(int[] ary, int from, int to)
    {
        if(from >= to) return;
        int mid = (from + to) / 2;
        mergesort(ary, from, mid);
        mergesort(ary, mid + 1, to);
        merge(ary, from, to);
    }

    void merge(int[] ary, int from, int to)
    {
        int[] copy = new int[to - from + 1];
        int mid = (from + to) / 2, i = from, j = mid + 1, idx = 0,
            inf = 1001;
        while(i < mid + 1 || j < to + 1)
        {
            if(i == mid + 1) copy[idx++] = ary[j++];
            else if(j == to + 1) copy[idx++] = ary[i++];
            else
            {
                int a = ary[i], b = ary[j];
                if(compare(a, b))
                {
                    copy[idx++] = a;
                    i++;
                }
                else
                {
                    copy[idx++] = b;
                    j++;
                }
            }

        }
        for(i = 0; i < idx; i++)
        {
            ary[i + from] =  copy[i];
        }
    }
}

插入排序

$O(nlgn)$

这个是看了大雪菜视频突然想到的, 也很有道理. insertion 排序只需要找到正确的插入位置即可.

其实用list我也并不能确定插入时间足够快, 按理来说是O[n]

Java 代码

// The compare API is defined in the parent class Relation:
//      boolean compare(int a, int b);
//      return boolean means whether a is less than b.

class Solution extends Relation {
    int k = 1;
    public int[] specialSort(int N) {
        int[] res = new int[N];
        List<Integer> list = new ArrayList<>();
        for(int i = 1; i <= N; i++)
        {
            int lo = 0, hi = k - 1;
            while(lo < hi)
            {
                int m = (lo + hi) / 2;
                if(compare(list.get(m), i)) lo = m + 1;
                else hi = m;
            }
            list.add(lo, i);
            k++;
        }
        for(int i = 0; i < N; i++) res[i] = list.get(i);
        return res;
    }
}