美女扒开粉嫩的尿囗给男生桶,插穴无码,91狠狠综合久久久久久,18禁乱伦,亚洲精品A片,av资源站,天天爽天天日天天射天天舔天天操天天射天天搞 ,国产免费一级A片

算法的重要性，我就不多說了吧，想去大廠，就必須要經過基礎知識和業(yè)務邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做?滑動窗口中位數，我們先來看題面：

https://leetcode-cn.com/problems/sliding-window-median/

中位數是有序序列最中間的那個數。如果序列的長度是偶數，則沒有最中間的數；此時中位數是最中間的兩個數的平均數。

例如：

[2,3,4]，中位數是 3

[2,3]，中位數是 (2 + 3) / 2 = 2.5

給你一個數組 nums，有一個長度為 k 的窗口從最左端滑動到最右端。窗口中有 k 個數，每次窗口向右移動 1 位。你的任務是找出每次窗口移動后得到的新窗口中元素的中位數，并輸出由它們組成的數組。

示例? ? ? ? ? ? ? ? ? ? ? ? ?

解題

https://www.cnblogs.com/kexinxin/p/10372465.html

題目會給一個數組，和一個滑動窗口的大小K，讓你找出當這個窗口滑動的過程中，這個K的窗口內的中位數分別是多少？

最naive的方式就是在k個窗口內排序就好，這里不解釋（因為開銷很大啊，(n-k+1) * (k*log(k))。。

這里的方法是使用兩個優(yōu)先隊列，即出隊列的順序是按照某種排好序的方式進行的。

所以我們設立兩個優(yōu)先隊列，這里叫做堆吧：

1、最大堆，值大的先出來

2、最小堆：值小的先出來

那么回到我們的問題，我們想想如何確定中位數：

1、假設我們有上述最大堆，最小堆

2、如果我們把進入的所有值較小的一半放到最大堆，較大的一半放到最小堆中，那么較小的那一半poll出來的，和較大那一半poll出來的，不正好是k個窗口的中位數的候選值么？

3、按照上面那個思想，我們就行動，再輸入值得時候，根據其大小，放入最大堆或者最小堆中，然后調整一些大小，保證最大堆那邊的大小等于或者多一個于最小堆

4、當輸出的時候，也就是從最大堆取一個，或者雙方各取一個就可以計算了

5、刪除的時候，在對應的堆中刪除，再按照3中的方式更新下就好

import java.util.Collections;
import java.util.PriorityQueue;

public?class?Solution?{
????public?double[] medianSlidingWindow(int[] nums, int?k) {
????????int?n = nums.length;
????????int?m = n - k + 1;
????????// 結果的尺寸
????????double[] res = new?double[m];
????????//兩個堆，一個最大堆，一個最小
????????PriorityQueue maxHeap = new?PriorityQueue(k, Collections.reverseOrder());
????????PriorityQueue minHeap = new?PriorityQueue(k);
????????for?(int?i = 0; i????????????int?num = nums[i];
????????????// 讓maxHeap始終保存小于一半的值，minHeap保存大于一半的，正好兩半
????????????if( maxHeap.size() == 0?|| maxHeap.peek() >= num) maxHeap.add(num);
????????????else?minHeap.add(num);
????????????// 維護兩個堆，保證兩個堆得大小，要么保持一致（偶數時），要么maxHeap多一個（奇數時）
????????????if( minHeap.size() > maxHeap.size() ) maxHeap.add(minHeap.poll());
????????????if( maxHeap.size() > minHeap.size() + 1?) minHeap.add(maxHeap.poll());
????????????// 如果需要輸出
????????????if?( i-k+1?>=0?){
????????????????if( k % 2?== 1?) res[i- k + 1] = maxHeap.peek();
????????????????else?res[i- k + 1] = (maxHeap.peek()/2.0?+ minHeap.peek()/2.0);
????????????????// 小心溢出
????????????????// 移除并更新
????????????????int?toBeRemove = nums[i - k + 1];
????????????????if( toBeRemove <= maxHeap.peek()) maxHeap.remove(toBeRemove);
????????????????else?minHeap.remove(toBeRemove);
????????????????// 維護兩個堆，保證兩個堆得大小，要么保持一致（偶數時），要么maxHeap多一個（奇數時）
????????????????if( minHeap.size() > maxHeap.size() ) maxHeap.add(minHeap.poll());
????????????????if( maxHeap.size() > minHeap.size() + 1?) minHeap.add(maxHeap.poll());
????????????}
????????}
????????return?res;
????}
}