成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[LintCode/LeetCode] Find Median From / Data Stream

zxhaaa / 3171人閱讀

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

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，使之成為一個最大堆。我們把遍歷過的數(shù)組元素對半分到兩個堆里，更大的數(shù)放在最小堆，較小的數(shù)放在最大堆。為什么這么分呢？因為要從maxHeap堆頂取較小的一半元素中最大的那個，而對另一半較大的數(shù)，我們并不關(guān)心。
同時，確保最大堆的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();
    }
};

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65100.html

相關(guān)文章

  • [LintCode/LeetCode] Sliding Window Maximum/Median

    摘要：窗口前進，刪隊首元素保證隊列降序加入當前元素下標從開始，每一次循環(huán)都將隊首元素加入結(jié)果數(shù)組 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 評論0 收藏0

  • [LintCode/LeetCode] Median of two Sorted Arrays

    摘要：由于要求的時間，所以選擇二分法。思路是找到兩個數(shù)組合并起來的第個元素。這樣只需計算兩個數(shù)組的中位數(shù)是第幾個元素，代入功能函數(shù)即可。據(jù)此，根據(jù)二分法的性質(zhì)，我們在遞歸時可以將前即個元素排除。 Problem There are two sorted arrays A and B of size m and n respectively. Find the median of the tw...

    vvpvvp 評論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 評論0 收藏0

  • leetcode295. Find Median from Data Stream

    摘要：思路和代碼這里采用了兩個優(yōu)先隊列來實現(xiàn)。一個優(yōu)先隊列用來存儲字符流中較小的一半，另一個用來存儲字符流中數(shù)值較大的一半。這樣當需要獲取當前中位數(shù)時，就可以根據(jù)當前的數(shù)值個數(shù)選擇一個或是兩個數(shù)的平均值。 題目要求 Median is the middle value in an ordered integer list. If the size of the list is even, t...

    microcosm1994 評論0 收藏0

  • [Leetcode] Find Median from Data Stream 數(shù)據(jù)流中位數(shù)

    摘要：最大堆存的是到目前為止較小的那一半數(shù)，最小堆存的是到目前為止較大的那一半數(shù)，這樣中位數(shù)只有可能是堆頂或者堆頂兩個數(shù)的均值。我們將新數(shù)加入堆后，要保證兩個堆的大小之差不超過。最大堆堆頂大于新數(shù)時，說明新數(shù)將處在所有數(shù)的下半部分。 Data Stream Median 最新更新：https://yanjia.me/zh/2019/02/... Median is the middle v...

    heartFollower 評論0 收藏0

發(fā)表評論

0條評論

zxhaaa

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<