2014年3月2日 星期日

[algorithm] get median

之前面試被問到的題目,在可以把全部資料放進一台機器記憶體內的時候,可以用一個min heap和一個max heap去記錄數列比較大的一半和比較小的一半,那時候寫的code是這樣

後來發現每次都先加到lower part的max heap再根據heap大小看要不要把root移到min heap是錯的。因為有可能一開始都是lower part的元素,結果有一些就這樣被移到upper part然後就在也回不來了。正確的是要一直維持一個目前的median值,比median大的就先加到upper part,比median小的加到lower part。然後再根據兩個heap大小去搬移root。這樣才可以維持「upper part的值都比lower part的值大」的性質。


沒有留言: