0

我正在为 coursera 相关课程做这个作业，并且是 Java、DS 和 Algo 的新手。我不会在这里粘贴我的整个代码。但下面是我在相关代码中面临的问题。

因此，要检索我正在使用的中位数PriorityQueue和Comparator接口。从下面的函数中，我尝试制作两个PriorityQueues，例如对于 21 个元素，hLow优先级队列有 11 个最小的元素，而hHigh有 10 个最高的元素。

public static void addToStream (int k) {
    hLow.add (k);
    if (hLow.size() > (hHigh.size() + 1)) {
        hHigh.add(hLow.poll());
    }
}

我写的比较器功能hLow是

hLComp = new Comparator <Integer> () {
        public int compare (Integer o1, Integer o2) {
            return o1.compareTo(o2);
        }   
    };

而对于hHigh是

hHComp = new Comparator <Integer> () {
        public int compare (Integer o1, Integer o2) {
            return -o1.compareTo(o2);
        }   
    };

我面临的问题是

hHigh.add(hLow.poll())

检索错误的值。例如，如果第一个值是 3000，那么这就是中位数，但是当第二个值出现时，例如是 6000。然后代码进入 if 条件，然后hHigh.peek显示 3000 并hLow.peek显示 6000。这与我的相反预计。

4

3 回答 3

1

这是一个完整的班级，其中有一个寻找中位数的例子。

public class Median {

    static PriorityQueue<Integer> hHigh  = new PriorityQueue<Integer>(100, 
            new Comparator<Integer>() {
        public int compare (Integer o1, Integer o2) {
            return o1.compareTo(o2);
        }
    });

    static PriorityQueue<Integer> hLow  = new PriorityQueue<Integer>(100, 
            new Comparator<Integer>() {
        public int compare (Integer o1, Integer o2) {
            return -o1.compareTo(o2);
        }
    });

    public static void addToStream (int k) {
        if (hHigh.size() == 0 || k > hHigh.peek()){
            hHigh.add(k);
        }

        else {
            hLow.add(k);
        }

        if (hLow.size() > (hHigh.size() + 1)) {
            hHigh.add(hLow.poll());
        }
        if (hHigh.size() > hLow.size()){
            hLow.add(hHigh.poll()); 
        }
    }

    public static void main(String[] args) {
        addToStream(3104);
        addToStream(6185);
        addToStream(7818);
        addToStream(2106);
        addToStream(5480);
        System.out.println(hLow.peek());
    }
}

该程序打印出：5480

于 2012-07-26T10:30:35.903 回答
1

上面的方法是有问题的。试试 5 4 3 你会看到的。该算法需要基本情况​​。这里解释得很好：

从整数流中查找运行中位数

于 2013-04-04T07:47:05.667 回答
0

每个队列中的值将按照您实现比较器的方式进行排序。您实现的方式是添加功能，您只需在 hLow 中放置一个，而不是在 hHigh 中放置一个。

如果要将较大的一半保留在一个队列中，而将另一半保留在第二个队列中，则需要比较每个队列头部的值。根据结果​​，您可能需要在队列之间进行交换，就像您输入的数字一样。

试试这个添加功能：

首先，您需要将 hLow 比较器分配给 hHigh，反之亦然。然后在添加值后 hLow.peek() 给你中位数。

public static void addToStream (int k) {
    if (hHigh.size() == 0 || k > hHigh.peek()){
        hHigh.add(k);
    }

    else {
        hLow.add(k);
    }

    if (hLow.size() > (hHigh.size() + 1)) {
        hHigh.add(hLow.poll());
    }
    if (hHigh.size() > hLow.size(){
        hLow.add(hHigh.poll()); 
    }
}
于 2012-07-25T22:57:32.030 回答