男女啪啪网站免费,国模乳神张雪馨私拍视频,无码区免费看一级毛片A片,国产精品igao,免费又色又爽无遮挡的扒胸罩,国产午夜精品在线观看,色婷婷国产精品秘免费网站,久久久人人人

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

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

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

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

例如：

[2,3,4]，中位數(shù)是 3

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

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

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

解題

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

題目會給一個數(shù)組，和一個滑動窗口的大小K，讓你找出當(dāng)這個窗口滑動的過程中，這個K的窗口內(nèi)的中位數(shù)分別是多少？

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

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

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

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

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

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

1、假設(shè)我們有上述最大堆，最小堆

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

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

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

5、刪除的時候，在對應(yīng)的堆中刪除，再按照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;
????????// 結(jié)果的尺寸
????????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);
????????????// 維護兩個堆，保證兩個堆得大小，要么保持一致（偶數(shù)時），要么maxHeap多一個（奇數(shù)時）
????????????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);
????????????????// 維護兩個堆，保證兩個堆得大小，要么保持一致（偶數(shù)時），要么maxHeap多一個（奇數(shù)時）
????????????????if( minHeap.size() > maxHeap.size() ) maxHeap.add(minHeap.poll());
????????????????if( maxHeap.size() > minHeap.size() + 1?) minHeap.add(maxHeap.poll());
????????????}
????????}
????????return?res;
????}
}