[LeetCode] 480. Sliding Window Median

freecode 發布于2019-08-16 14:01 / 2844人閱讀

摘要：存大于的數存小于的數保證總比的相等或多一個元素

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 value.

Examples:
[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

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 see the k numbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Median
---------------               -----
[1  3  -1] -3  5  3  6  7       1
 1 [3  -1  -3] 5  3  6  7       -1
 1  3 [-1  -3  5] 3  6  7       -1
 1  3  -1 [-3  5  3] 6  7       3
 1  3  -1  -3 [5  3  6] 7       5
 1  3  -1  -3  5 [3  6  7]      6

Therefore, return the median sliding window as [1,-1,-1,3,5,6].

Note:
You may assume k is always valid, ie: k is always smaller than input array"s size for non-empty array.

Solution

class Solution {
    //minHeap存大于median的數
    //maxHeap存小于median的數
    PriorityQueue minHeap = new PriorityQueue<>();
    PriorityQueue maxHeap = new PriorityQueue<>((a, b)->(b.compareTo(a)));
    public double[] medianSlidingWindow(int[] nums, int k) {
        int n = nums.length-k+1;
        if (n <= 0) return new double[0];
        
        double[] res = new double[n];
        
        for (int i = 0; i <= nums.length; i++) {
            if (i >= k) {
                res[i-k] = getMedian();
                remove(nums[i-k]);
            }
            if (i < nums.length) {
                add(nums[i]);
            }
        }
        
        return res;
    }
    private void add(int num) {
        if (num < getMedian()) maxHeap.offer(num);
        else minHeap.offer(num);
        //保證minHeap總比maxHeap的size相等或多一個元素
        if (maxHeap.size() > minHeap.size()) minHeap.offer(maxHeap.poll());
        if (maxHeap.size() < minHeap.size()-1) maxHeap.offer(minHeap.poll());
    }
    private void remove(int num) {
        if (num < getMedian()) maxHeap.remove(num);
        else minHeap.remove(num);
        if (maxHeap.size() > minHeap.size()) minHeap.offer(maxHeap.poll());
        if (maxHeap.size() < minHeap.size()-1) maxHeap.offer(minHeap.poll());
    }
    private double getMedian() {
        if (maxHeap.isEmpty() && minHeap.isEmpty()) return 0;
        if (maxHeap.size() == minHeap.size()) return ((double) maxHeap.peek() + (double) minHeap.peek()) / 2.0;
        else return (double) minHeap.peek();
    }
}

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

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

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

480. Sliding Window Median

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

Scorpion 2019-08-16 10:28 評論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
[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
leetcode239. Sliding Window Maximum

摘要：題目要求假設有一個數組和一個長度為的窗口，數組長度。當窗口右滑時，會刪除下標上的值，并加入下標上的值。此時中記錄的值編程了，并返回當前的最大值為。一旦最大值失效，就從窗口中重新找一個最大值就好了。題目要求 Given an array nums, there is a sliding window of size k which is moving from the very lef...

sPeng 2019-08-15 14:22 評論0 收藏0
[Leetcode] Sliding Window Maximum 滑動窗口最大值

摘要：這樣，我們可以保證隊列里的元素是從頭到尾降序的，由于隊列里只有窗口內的數，所以他們其實就是窗口內第一大，第二大，第三大的數。 Sliding Window Maximum Given an array nums, there is a sliding window of size k which is moving from the very left of the array to...

lvzishen 2019-08-14 12:46 評論0 收藏0