[LintCode/LeetCode] Find Median From / Data Stream

zxhaaa 發布于2019-08-14 14:35 / 3147人閱讀

摘要：建立兩個堆，一個堆就是本身，也就是一個最小堆另一個要寫一個，使之成為一個最大堆。我們把遍歷過的數組元素對半分到兩個堆里，更大的數放在最小堆，較小的數放在最大堆。同時，確保最大堆的比最小堆大，才能從最大堆的頂端返回。

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();
    }
};

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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