相关疑难解决方法(0)

我写了一个简单的程序,在O(n)中排序.它的内存效率很低,但这不是重点.

它使用了背后的原理HashMap进行排序:

public class NLogNBreak {
    public static class LinkedListBack {
        public LinkedListBack(int val){
            first = new Node();
            first.val = val;
        }
        public Node first = null;
        public void insert(int i){
            Node n = new Node();
            n.val = i;
            n.next = first;
            first = n;
        }
    }

    private static class Node {
        public Node next = null;
        public int val;
    }

    //max > in[i] > 0
    public static LinkedListBack[] sorted(int[] in, int max){
        LinkedListBack[] ar = new LinkedListBack[max …

我认为我知道答案,最小的复杂性是O(nlogn).

但是,有没有什么办法可以在O(n)复杂度中从堆中创建二进制搜索树？