跟踪扩展阵列的中位数

Question

面试问题:

编辑下面 你给了一个数组.你从它做出2个堆,一个minheap和另一个最大堆.现在在O(nlog n)时间内使用这2个提供的堆找到数组的中值.

更正的问题 编号随机生成并存储到(扩展)数组中.你会如何跟踪中位数？

解决方案 使用2个堆可以解决此问题,并且可以在O(1)时间内始终访问中值.

Answer 1

这是你如何使用两个堆.请注意,我假设您不知道元素的数量,这就是为什么我们必须弹出,直到我们从最小堆中弹出大于或等于我们从最大堆弹出的内容.请注意,我们返回平均值,因为在{1, 2, 3, 4}实际上是中位数的情况下2.5(两个"中间"值的平均值).我假设double作为值类型,但这显然可以是任何东西.这里:

double min = minheap.pop();
double max = maxheap.pop();
while(min < max) {
    min = minheap.pop();
    max = maxheap.pop();
}

return (min + max) / 2;

因为弹出是O(log n),我们必须弹出O(n / 2)值,这是O(n log n).

Answer 2

Java 中的一个工作实现，使用 2 个堆，O(n log n)。在任何时候我都会保持两个堆的大小平衡（即，如果我们输入 n 个元素使得 n%2==1，它们最多相差 1）。获得中位数是 O(1)。添加一个新元素是 O(log n)。

public class MedianOfStream {

    private int count;
    private PriorityQueue<Integer> highs, lows;

    public MedianOfStream() {
        highs = new PriorityQueue<Integer>(11, new Comparator<Integer>() {
            @Override
            public int compare(Integer arg0, Integer arg1) {
                return arg0.compareTo(arg1);
            }
        });
        lows = new PriorityQueue<Integer>(11, new Comparator<Integer>() {
            @Override
            public int compare(Integer arg0, Integer arg1) {
                return arg1.compareTo(arg0);
            }
        });
    }

    private int getMedian() {
        if (count == 0)
            return 0;
        if (lows.size() == highs.size()) {
            return (lows.peek() + highs.peek()) / 2;
        } else if (lows.size() < highs.size()) {
            return highs.peek();
        }
        return lows.peek();
    }

    private void swap(){
        int h = highs.poll();
        int l = lows.poll();
        highs.add(l);
        lows.add(h);
    }

    public int updateMedian(int n) {
        count++;

        if (count == 1)
            lows.add(n);

        else if (count==2) {
            highs.add(n);
            if(highs.peek()<lows.peek()) {
                swap(); // O(log n)
            }
        }

        else {
            if (n > highs.peek()) {
                lows.add(highs.poll()); // O(log n)
                highs.add(n); // O(log n)
            } else {
                highs.add(lows.poll()); // O(log n)
                lows.add(n); // O(log n)
            }
            if(highs.peek()<lows.peek()) {
                swap(); // O(log n)
            }
        }

        // if we added an even # of items,
        // the heaps must be exactly the same size,
        // otherwise we tolerate a 1-off difference

        if (Math.abs(lows.size() - highs.size()) > (count % 2)) {
            if (lows.size() < highs.size()) {
                lows.add(highs.poll()); // O(log n)
            } else {
                highs.add(lows.poll()); // O(log n)
            }
        }

        return getMedian(); // O(1)
    }
}

Answer 3

从堆中弹出是一个 O(log N) 操作，因此您可以通过从其中一个堆中弹出一半元素并获取最后弹出的值来实现 O(N log N)（您必须处理边缘情况）。但这并没有利用其他堆。

使用选择算法可以实现 O(N) ，但常数因子非常高。如果您已经有堆，前一个建议可能会更好。