【題目描述】
Given an array of n integer, and a moving window(size k), move the window at each iteration from the start of the array, find the median of the element inside the window at each moving. (If there are even numbers in the array, return the N/2-th number after sorting the element in the window. )
給定一個(gè)包含 n 個(gè)整數(shù)的數(shù)組旁振，和一個(gè)大小為k的滑動(dòng)窗口,從左到右在數(shù)組中滑動(dòng)這個(gè)窗口算柳，找到數(shù)組中每個(gè)窗口內(nèi)的中位數(shù)超歌。(如果數(shù)組個(gè)數(shù)是偶數(shù)研铆，則在該窗口排序數(shù)字后丽声，返回第 N/2 個(gè)數(shù)字躬充。)
【題目鏈接】
www.lintcode.com/en/problem/sliding-window-median/
【題目解析】
這道題和Data Stream Median類似醋寝，也是尋找動(dòng)態(tài)數(shù)組的media丽惶，因此也可以用maxheap＋minheap來解譬胎。隨著窗口的移動(dòng)差牛，每次先加入一個(gè)新元素，再刪去一個(gè)舊元素堰乔，再使兩個(gè)heap中元素?cái)?shù)量平衡即可偏化。
用一個(gè)最大堆來記錄較小一半的元素，一個(gè)最小堆來記錄較大一半的元素镐侯。
先初始化最初的窗口里的k個(gè)元素侦讨。將元素加入最大堆，若為奇數(shù)次，則比較最大堆堆頂和最小堆堆頂元素大小韵卤，若最大堆堆頂元素大于和最小堆堆頂元素骗污，則交換兩個(gè)堆頂元素，若為偶數(shù)次沈条，則將最大堆堆頂元素加入最小堆需忿。
然后開始移動(dòng)窗口，先將新元素加入蜡歹，若比原median小贴谎，則加入最大堆，反之則加入最小堆季稳。然后刪除窗口最前面的一個(gè)元素。
然后調(diào)整最大堆和最小堆的大小澈魄。根據(jù)k值可以分兩種情況討論：
1）若k為偶數(shù)景鼠，則需要最大堆中元素和最小堆中元素?cái)?shù)量相等
2）若k為奇數(shù)，則需要最大堆中元素比最小堆中元素多1個(gè)
此時(shí)最大堆的堆頂元素即為此時(shí)窗口元素的median
【參考答案】
