資訊專欄INFORMATION COLUMN
摘要：存大于的數(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 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.
class Solution {
//minHeap存大于median的數(shù)
//maxHeap存小于median的數(shù)
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相等或多一個(gè)元素
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();
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/72738.html
摘要：題目鏈接這題和那道比起來多加了個(gè)。還是用兩個(gè)來做，這個(gè)操作復(fù)雜度用了。和，在保存較小的一半元素，保存較大的一半元素，，注意寫的時(shí)候不能用，因?yàn)榭赡?。沒想出來其他方法，參考的解法 480. Sliding Window Median 題目鏈接：https://leetcode.com/problems... 這題和那道Find Median from Data Stream比起來多加了個(gè)...
摘要：窗口前進(jìn)，刪隊(duì)首元素保證隊(duì)列降序加入當(dāng)前元素下標(biāo)從開始，每一次循環(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...
摘要：丟棄隊(duì)首那些超出窗口長度的元素隊(duì)首的元素都是比后來加入元素大的元素，所以存儲(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...
摘要：題目要求假設(shè)有一個(gè)數(shù)組和一個(gè)長度為的窗口，數(shù)組長度。當(dāng)窗口右滑時(shí)，會(huì)刪除下標(biāo)上的值，并加入下標(biāo)上的值。此時(shí)中記錄的值編程了，并返回當(dāng)前的最大值為。一旦最大值失效，就從窗口中重新找一個(gè)最大值就好了。 題目要求 Given an array nums, there is a sliding window of size k which is moving from the very lef...
摘要：這樣，我們可以保證隊(duì)列里的元素是從頭到尾降序的，由于隊(duì)列里只有窗口內(nèi)的數(shù)，所以他們其實(shí)就是窗口內(nèi)第一大，第二大，第三大的數(shù)。 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...
閱讀 1157·2021-11-18 10:02
閱讀 1389·2021-09-23 11:22
閱讀 2769·2021-08-21 14:08
閱讀 1723·2019-08-30 15:55
閱讀 1805·2019-08-30 13:45
閱讀 3354·2019-08-29 16:52
閱讀 3181·2019-08-29 12:18
閱讀 1728·2019-08-26 13:36
