295. 数据流的中位数

题目描述

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) – 从数据流中添加一个整数到数据结构中。
double findMedian() – 返回目前所有元素的中位数。

示例：

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

进阶:

如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？

https://leetcode-cn.com/problems/find-median-from-data-stream/

解法1

寻找合适的位置插入元素，我们可以顺序搜索或者二分搜索(Binary Search)。为了尽可能优化我们的朴素算法，我们在这里使用二分搜索，使得寻找插入点的时间复杂度从O(n)降到O(logn)。但是向ArrayList中插入元素涉及到元素的移动，时间复杂度为O(logn) + O(n) == O(n)。如果我们使用LinkedList，我们将无法使用二分搜索，即使插入元素的时间复杂度为O(1)。

下面说一下如何利用二分查找找到合适的插入位置。为了插入元素num，我们需要寻找位置i，使得nums[i-1] < num且nums[i] > num。找到这么一个位置后，我们在i的前方插入元素num，就使得数组nums仍然是有序。对于二分查找，我们使用“左闭右开”（记为[l, r)）的实现方式。计算m = (l + r) >>> 1（等价于(l+r) / 2，但是不会溢出）。当nums[m] > num && nums[m – 1] < num，则m就是合适的位置；如果nums[m] < num && nums[m+1] > num，则m+1就是合适位置；当nums[m] == num，则m就是合适位置；如果找不到这么一个位置，我们就将插入的元素追加到数组的最后一个位置。

插入一个元素的时间复杂度为O(n)，需要向数组重插入n个元素，那么整体的时间复杂度为O(n^2)，空间复杂度O(n)。全部代码如下：

import java.util.ArrayList;
import java.util.List;

class MedianFinder {
    List<Integer> nums;

    public MedianFinder() {
        nums = new ArrayList<>();
    }

    public void addNum(int num) {
        int l = 0, r = nums.size();
        int pos = -1;

        while (l < r) {
            int m = (l + r) >>> 1;

            if (nums.get(m) > num) {
                if (m - 1 >= l && nums.get(m - 1) < num) {
                    pos = m;
                    break;
                } else
                    r = m;
            } else if (nums.get(m) < num) {
                if (m + 1 < r && nums.get(m + 1) > num) {
                    pos = m + 1;
                    break;
                } else
                    l = m + 1;
            } else {
                pos = m;
                break;
            }
        }
        if (l == r)
            pos = l;
        nums.add(pos, num);
    }

    public double findMedian() {
        if (nums.size() % 2 == 0) {
            return (nums.get(nums.size() / 2 - 1) + nums.get(nums.size() / 2)) / 2.0;
        } else {
            return nums.get(nums.size() / 2);
        }
    }
}

解法2

解法2使用两个堆，一个大顶堆（Max heap），一个小顶堆（Min heap），且使得大顶堆的元素个数始终大于等于小顶堆，且不多于一个元素。我们将插入的元素均分到大顶堆和小顶堆中，取大顶堆最大的元素与小顶堆最小的元素取平均就是中位数（偶数个元素情况），否则取大顶堆最大元素作为中位数（奇数个元素）。

图1以插入序列为 {1, 3, 4, 5, 6}为例，画出了堆的变化过程。我们首先将待插入的元素num与Max heap的最大元素对比，如果小于Max heap的最大元素，就插入到Max heap中，否则插入到Min heap中。当插入操作完后，检查Max heap与Min heap的元素个数，使得Max heap的元素个数大于等于Min heap，且不多于1个元素，否则我们需要进行平衡操作。平衡操作可能将Max heap的最大元素搬到Min heap；也可能将Min heap的最小元素搬到Max heap，使得0<=|Max heap| – |Min heap| < =1。

当需要计算中位数时，我们检查Max heap与Min heap的元素总数。如果是奇数个元素，则取Max heap中最大元素；如果是偶数个元素，取Max heap中最大元素与Min heap中最小元素取平均。

在实现方面，使用Java语言内置的PriorityQueue就能够实现Max heap与Min heap。如果使用默认构造函数，则是Min heap，如果想实现Max heap我们可以传入Collections.reverseOrder()到PriorityQueue的构造函数中。

解法2插入元素的时间复杂度为O(logn)，插入n个元素的时间复杂度为O(nlogn);寻找中位数的时间复杂度为O(1)。全部代码如下：

import java.util.Collections;
import java.util.PriorityQueue;

class MedianFinder {
    PriorityQueue<Integer> minHeap;
    PriorityQueue<Integer> maxHeap;

    public MedianFinder() {
        minHeap = new PriorityQueue<>();
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    }

    public void addNum(int num) {
        if (maxHeap.isEmpty() || maxHeap.peek() > num)
            maxHeap.offer(num);
        else
            minHeap.offer(num);

        // we keep 0<=|maxHeap| - |minHeap|<=1
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        } else if (maxHeap.size() - minHeap.size() >= 2) {
            minHeap.offer(maxHeap.poll());
        }
    }

    public double findMedian() {
        if ((maxHeap.size() + minHeap.size()) % 2 == 0)
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        else
            return maxHeap.peek();
    }
}

解法3

解法3使用一种比较自然的方法，我们使用TreeMap存放插入的数组元素，使用l指针和r指针跟踪TreeMap中的中间元素。如果向TreeMap插入新元素，我们需要维护l与r指针。当需要寻找中位数时，我们直接求(l+r) / 2即可，而不需要区分奇数偶数个元素情况，因为奇数元素时l与r指针将会指向同一个元素。

在实现中，还有另一个问题需要考虑。Java提供的TreeMap不能支持重复元素的插入，为了记录重复元素的信息，我们将TreeMap声明为Tree<Integer, Integer>，key为插入的元素，value为元素重复的次数。我们将l与r指针声明为一维数组int[]，第0个元素表示数组中数字本身，第1个元素表示指向重复元素的数字的第几个（rank）。

当插入元素后，为了维护l与r指针，且始终r>=l。我们分为了4种case。我们将插入元素记为num：

插入前奇数个元素，num >= l/r (此时l==r)
插入前奇数个元素，num < l/r
插入前偶数个元素，num >= r
插入前偶数个元素，num < r

图3列出了插入前奇数个元素的case，如果num>= l/r，需要将r++；否则将l–。

图4列出了插入前偶数个元素的case，如果num>=r，需要将l++；否则将r–且让l=r。

需要注意得是，这里的l++、l–、r++、r–指的是调整l、r的指针，但是我们将插入的元素存入到TreeMap中（而不是数组中，TreeMap是逻辑有序，但物理上用红黑树存储），我们需要调用TreeMap的higher/lower函数来改变l、r的指向，这两个操作的时间复杂度为O(logn)而不是O(1)。

为了实现l/r++操作与l/r–操作，我们实现了两个函数after(ptr)与before(ptr)。ptr就是一维数组，第0个元素表示key，第1个元素表示出现在第几个位置（因为元素会重复）。

private int[] after(int[] ptr) {
    int dupTimes = treeMap.get(ptr[0]);

    if (ptr[1] < dupTimes)
        return new int[]{ptr[0], ptr[1] + 1};
    else
        return new int[]{treeMap.higherKey(ptr[0]), 1};
}

private int[] before(int[] ptr) {
    if (ptr[1] > 1)
        return new int[]{ptr[0], ptr[1] - 1};
    else {
        Map.Entry<Integer, Integer> keyTimes = treeMap.lowerEntry(ptr[0]);
        return new int[]{keyTimes.getKey(), keyTimes.getValue()};
    }
}

该算法的插入时间复杂度为O(logn)，当有n个元素插入时，总的时间复杂度为O(nlogn)；寻找中位数的时间复杂度为O(1)。但是在测试中，解法3的运行时间与解法1的运行时间差不多（280ms+），这大概是由于创建对象导致的overhead，而解法2运行时间最短（180ms+）。全部代码如下：

import java.util.Map;
import java.util.TreeMap;

class MedianFinder {
    private TreeMap<Integer, Integer> treeMap; // value, duplicated times
    private int size;
    private int[] l = {0, 0}, r = {0, 0};    // elem, rank of duplicated element

    public MedianFinder() {
        treeMap = new TreeMap<>();
    }

    private int[] after(int[] ptr) {
        int dupTimes = treeMap.get(ptr[0]);

        if (ptr[1] < dupTimes)
            return new int[]{ptr[0], ptr[1] + 1};
        else
            return new int[]{treeMap.higherKey(ptr[0]), 1};
    }

    private int[] before(int[] ptr) {
        if (ptr[1] > 1)
            return new int[]{ptr[0], ptr[1] - 1};
        else {
            Map.Entry<Integer, Integer> keyTimes = treeMap.lowerEntry(ptr[0]);
            return new int[]{keyTimes.getKey(), keyTimes.getValue()};
        }
    }

    public void addNum(int num) {
        treeMap.merge(num, 1, (a, b) -> a + b);

        size++;

        if (size == 1) {
            l = r = new int[]{num, 1};
        } else {
            // we should use size instead of treeMap.size cause by duplicated elements
            if (size % 2 == 0) {
                // treemap has odd numbers before insertion
                // As l == r, let l or r be here is okay
                if (num >= l[0])
                    r = after(r);
                else
                    l = before(l);
            } else {
                // treemap has even numbers before insertion
                if (num >= r[0])
                    l = after(l);
                else {
                    r = before(r);
                    l = r;
                }
            }
        }
    }

    public double findMedian() {
        return (l[0] + r[0]) / 2.0;
    }
}

参考：https://zxi.mytechroad.com/blog/leetcode/leetcode-295-find-median-from-data-stream/

Liang' Blog

295. 数据流的中位数

题目描述

解法1

解法2

解法3

Leave a Reply Cancel reply