国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專(zhuān)欄INFORMATION COLUMN

480. Sliding Window Median

Scorpion / 1660人閱讀

摘要：題目鏈接這題和那道比起來(lái)多加了個(gè)。還是用兩個(gè)來(lái)做，這個(gè)操作復(fù)雜度用了。和，在保存較小的一半元素，保存較大的一半元素，，注意寫(xiě)的時(shí)候不能用，因?yàn)榭赡堋](méi)想出來(lái)其他方法，參考的解法

480. Sliding Window Median

題目鏈接：https://leetcode.com/problems...

這題和那道Find Median from Data Stream比起來(lái)多加了個(gè)sliding window。那道題巧妙的用了兩個(gè)heap來(lái)找到mean，還有道題是Slide Window Maximum，同樣是slide window的題。還是用兩個(gè)heap來(lái)做，remove這個(gè)操作復(fù)雜度用了logk。minHeap和maxHeap，maxHeap在保存較小的一半元素，minHeap保存較大的一半元素，0 <= minHeap.size() - maxHeap.size() <= 1，注意maxheap寫(xiě)的時(shí)候不能用a - b，因?yàn)榭赡躱verflow。

public class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        double[] result = new double[n - k + 1];
        maxHeap = new PriorityQueue<>(k/2 + 1, (a, b) -> b.compareTo(a));
        minHeap = new PriorityQueue<>(k/2 + 1);
        
        for(int i = 0; i < n; i++) {
            // delete the element beyond the window
            if(maxHeap.size() + minHeap.size() == k) slide(nums[i - k]);
            // add new element to the window
            add(nums[i]);
            if(i >= k - 1) {
                result[i - k + 1] = getMedian();
            }
        }
        
        return result;
    }
    
    PriorityQueue minHeap;
    PriorityQueue maxHeap;
    private void slide(int target) {
        if(minHeap.contains(target)) minHeap.remove(target);
        else maxHeap.remove(target);
    }
    
    private void add(int num) {
        maxHeap.add(num);
        minHeap.add(maxHeap.poll());
        if(maxHeap.size() + 1 < minHeap.size()) maxHeap.add(minHeap.poll());
    }
    
    private double getMedian() {
        // window size is even
        if(minHeap.size() == maxHeap.size()) return minHeap.peek()/2.0 + maxHeap.peek()/2.0;
        else return minHeap.peek();
    }
}

沒(méi)想出來(lái)其他方法，參考discussion的解法:
https://discuss.leetcode.com/...

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/69848.html

相關(guān)文章

  • [LeetCode] 480. Sliding Window Median

    摘要：存大于的數(shù)存小于的數(shù)保證總比的相等或多一個(gè)元素 Problem 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 valu...

    freecode 評(píng)論0 收藏0

  • [LintCode/LeetCode] Sliding Window Maximum/Median

    摘要：窗口前進(jìn)，刪隊(duì)首元素保證隊(duì)列降序加入當(dāng)前元素下標(biāo)從開(kāi)始，每一次循環(huán)都將隊(duì)首元素加入結(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 評(píng)論0 收藏0

  • 關(guān)于codahale的HistogramMetric

    摘要：百分位數(shù)第百分位數(shù)是這樣一個(gè)值，它使得至少有的數(shù)據(jù)項(xiàng)小于或等于這個(gè)值，且至少有的數(shù)據(jù)項(xiàng)大于或等于這個(gè)值。即使極值變動(dòng)大，相比其他幾個(gè)，還是比較接近實(shí)際數(shù)據(jù)，曲線會(huì)有明顯變動(dòng)，不像其他的一段時(shí)間可能都是平滑的。 基本概念 mean(平均值) 均值是就全部數(shù)據(jù)計(jì)算的,它具有優(yōu)良的數(shù)學(xué)性質(zhì),是實(shí)際中應(yīng)用最廣泛的集中趨勢(shì)測(cè)度值.其主要缺點(diǎn)是易受數(shù)據(jù)極端值的影響,對(duì)于偏態(tài)分布的數(shù)據(jù),均值的代表性...

    JiaXinYi 評(píng)論0 收藏0

  • [LeetCode] 239. Sliding Window Maximum

    摘要：丟棄隊(duì)首那些超出窗口長(zhǎng)度的元素隊(duì)首的元素都是比后來(lái)加入元素大的元素，所以存儲(chǔ)的對(duì)應(yīng)的元素是從小到大 Problem Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only...

    lentoo 評(píng)論0 收藏0

  • 一維滑動(dòng)窗口(SlidingWindow)

    摘要：滑動(dòng)窗口問(wèn)題經(jīng)常使用快慢指針的區(qū)域?yàn)榛瑒?dòng)窗口已經(jīng)探索過(guò)的區(qū)域的區(qū)域?yàn)榛瑒?dòng)窗口正在探索的區(qū)域?yàn)榇剿鞯膮^(qū)域的問(wèn)題主要分為和當(dāng)快指針增加的時(shí)候慢指針必須增加快指針增加，慢指針不一定變化使用滑動(dòng)窗口可以線性時(shí)間解決問(wèn)題而且可以減少空間消耗要求 滑動(dòng)窗口(Sliding Window)問(wèn)題經(jīng)常使用快慢指針(slow, fast pointer)[0, slow)?的區(qū)域?yàn)榛瑒?dòng)窗口已經(jīng)探索過(guò)的區(qū)...

    hlcfan 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<