成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

480. Sliding Window Median

Scorpion / 1717人閱讀

摘要：題目鏈接這題和那道比起來多加了個。還是用兩個來做，這個操作復(fù)雜度用了。和，在保存較小的一半元素，保存較大的一半元素，，注意寫的時候不能用，因為可能。沒想出來其他方法，參考的解法

480. Sliding Window Median

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

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

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

沒想出來其他方法，參考discussion的解法:
https://discuss.leetcode.com/...

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

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/69848.html

相關(guān)文章

  • [LeetCode] 480. Sliding Window Median

    摘要：存大于的數(shù)存小于的數(shù)保證總比的相等或多一個元素 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 評論0 收藏0

  • [LintCode/LeetCode] Sliding Window Maximum/Median

    摘要：窗口前進(jìn)，刪隊首元素保證隊列降序加入當(dāng)前元素下標(biāo)從開始，每一次循環(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

  • 關(guān)于codahale的HistogramMetric

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

    JiaXinYi 評論0 收藏0

  • [LeetCode] 239. Sliding Window Maximum

    摘要：丟棄隊首那些超出窗口長度的元素隊首的元素都是比后來加入元素大的元素，所以存儲的對應(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 評論0 收藏0

  • 一維滑動窗口(SlidingWindow)

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

    hlcfan 評論0 收藏0

發(fā)表評論

0條評論

閱讀需要支付1元查看
<