[LintCode/LeetCode] Find Median From / Data Stream

zxhaaa 发布于2019-08-14 14:35 / 3146人阅读

摘要：建立两个堆，一个堆就是本身，也就是一个最小堆另一个要写一个，使之成为一个最大堆。我们把遍历过的数组元素对半分到两个堆里，更大的数放在最小堆，较小的数放在最大堆。同时，确保最大堆的比最小堆大，才能从最大堆的顶端返回。

Problem

Numbers keep coming, return the median of numbers at every time a new number added.

Clarification

What"s the definition of Median?

Median is the number that in the middle of a sorted array. If there are n numbers in a sorted array A, the median is A[(n - 1) / 2]. For example, if A=[1,2,3], median is 2. If A=[1,19], median is 1.

Example

For numbers coming list: [1, 2, 3, 4, 5], return [1, 1, 2, 2, 3].

For numbers coming list: [4, 5, 1, 3, 2, 6, 0], return [4, 4, 4, 3, 3, 3, 3].

For numbers coming list: [2, 20, 100], return [2, 2, 20].

Challenge

Total run time in O(nlogn).

Tags

LintCode Copyright Heap Priority Queue Google

Note

建立两个堆，一个堆就是PriorityQueue本身，也就是一个最小堆；另一个要写一个Comparator，使之成为一个最大堆。我们把遍历过的数组元素对半分到两个堆里，更大的数放在最小堆，较小的数放在最大堆。为什么这么分呢？因为要从maxHeap堆顶取较小的一半元素中最大的那个，而对另一半较大的数，我们并不关心。
同时，确保最大堆的size比最小堆大1，才能从最大堆的顶端返回median。

Solution

public class Solution {
    public int[] medianII(int[] nums) {
        if (nums == null || nums.length == 0) return new int[0];
        int[] res = new int[nums.length];
        PriorityQueue minHeap = new PriorityQueue<>();
        PriorityQueue maxHeap = new PriorityQueue<>(16, new Comparator() {
            public int compare(Integer x, Integer y) {
                return y-x;
            }
        });
        res[0] = nums[0];
        maxHeap.add(nums[0]);
        for (int i = 1; i < nums.length; i++) {
            int max = maxHeap.peek();
            if (nums[i] <= max) maxHeap.add(nums[i]);
            else minHeap.add(nums[i]);
            if (maxHeap.size() > minHeap.size()+1) minHeap.add(maxHeap.poll());
            else if (maxHeap.size() < minHeap.size()) maxHeap.add(minHeap.poll());
            res[i] = maxHeap.peek();
        }
        return res;
    }
}

LeetCode Version

public class MedianFinder {
    PriorityQueue minheap = new PriorityQueue<>();
    PriorityQueue maxheap = new PriorityQueue<>(1, new Comparator() {
        public int compare(Integer i1, Integer i2) {
            return i2-i1;
        }
    });
    // Or we can use: = new PriorityQueue<>(1, Collections.reverseOrder());
    
    // Adds a number into the data structure.
    public void addNum(int num) {
        maxheap.offer(num);
        minheap.offer(maxheap.poll());
        if (maxheap.size() < minheap.size()) maxheap.offer(minheap.poll());
        else if (maxheap.size() > minheap.size()) minheap.offer(maxheap.poll());
        //or (maxheap.size() > minheap.size()+1)
    }

    // Returns the median of current data stream
    public double findMedian() {
        if(maxheap.size() == minheap.size()) return (maxheap.peek()+minheap.peek())/2.0;
        return maxheap.peek();
    }
};

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65100.html

[LintCode/LeetCode] Sliding Window Maximum/Median

摘要：窗口前进，删队首元素保证队列降序加入当前元素下标从开始，每一次循环都将队首元素加入结果数组 Sliding Window Maximum Problem Given an array of n integer with duplicate number, and a moving window(size k), move the window at each iteration fro...

crelaber 2019-08-14 14:33 评论0 收藏0
[LintCode/LeetCode] Median of two Sorted Arrays

摘要：由于要求的时间，所以选择二分法。思路是找到两个数组合并起来的第个元素。这样只需计算两个数组的中位数是第几个元素，代入功能函数即可。据此，根据二分法的性质，我们在递归时可以将前即个元素排除。 Problem There are two sorted arrays A and B of size m and n respectively. Find the median of the tw...

vvpvvp 2019-08-14 15:41 评论0 收藏0
[LeetCode]Find Median from Data Stream

Find Median from Data Stream Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value. Examp...

suemi 2019-08-14 15:08 评论0 收藏0
leetcode295. Find Median from Data Stream

摘要：思路和代码这里采用了两个优先队列来实现。一个优先队列用来存储字符流中较小的一半，另一个用来存储字符流中数值较大的一半。这样当需要获取当前中位数时，就可以根据当前的数值个数选择一个或是两个数的平均值。题目要求 Median is the middle value in an ordered integer list. If the size of the list is even, t...

microcosm1994 2019-08-15 14:42 评论0 收藏0
[Leetcode] Find Median from Data Stream 数据流中位数

摘要：最大堆存的是到目前为止较小的那一半数，最小堆存的是到目前为止较大的那一半数，这样中位数只有可能是堆顶或者堆顶两个数的均值。我们将新数加入堆后，要保证两个堆的大小之差不超过。最大堆堆顶大于新数时，说明新数将处在所有数的下半部分。 Data Stream Median 最新更新：https://yanjia.me/zh/2019/02/... Median is the middle v...

heartFollower 2019-08-14 12:28 评论0 收藏0