480. Sliding Window Median

Scorpion 发布于2019-08-16 10:28 / 1646人阅读

摘要：题目链接这题和那道比起来多加了个。还是用两个来做，这个操作复杂度用了。和，在保存较小的一半元素，保存较大的一半元素，，注意写的时候不能用，因为可能。没想出来其他方法，参考的解法

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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