題目:
輸入n個整數(shù)启摄,找出其中最小的k個數(shù)。
解法:
top K問題。
如果n不大,可以一次性載入內(nèi)存笔横,則用一個數(shù)組保存,然后進行多次partition()即可
如果n很大咐吼,無法一次性載入內(nèi)存吹缔,則構(gòu)建一個大頂堆(根結(jié)點比所有子結(jié)點都大),依次讀入n個數(shù)锯茄,并分別與堆頂元素做比較厢塘,如果比堆頂元素大,直接丟棄肌幽;如果比堆頂元素小晚碾,則替換堆頂元素。最后喂急,堆的元素即為所求格嘁。