480. Sliding Window Median

Scorpion 發布于2019-08-16 10:28 / 1666人閱讀

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

480. Sliding Window Median

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

這題和那道Find Median from Data Stream比起來多加了個sliding window。那道題巧妙的用了兩個heap來找到mean，還有道題是Slide Window Maximum，同樣是slide window的題。還是用兩個heap來做，remove這個操作復雜度用了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/...

GPU云服務器云服務器 Sliding Median 聯想y480 window

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

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/69848.html

[LeetCode] 480. Sliding Window Median

摘要：存大于的數存小于的數保證總比的相等或多一個元素 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 2019-08-16 14:01 評論0 收藏0
[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
關于codahale的HistogramMetric

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

JiaXinYi 2019-08-14 17:41 評論0 收藏0
[LeetCode] 239. Sliding Window Maximum

摘要：丟棄隊首那些超出窗口長度的元素隊首的元素都是比后來加入元素大的元素，所以存儲的對應的元素是從小到大 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 2019-08-16 13:45 評論0 收藏0
一維滑動窗口(SlidingWindow)

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

hlcfan 2019-08-15 13:47 評論0 收藏0