? 這是一道經(jīng)常在面試中被問(wèn)到的題目，要你設(shè)計(jì)一個(gè)算法，求一堆數(shù)中的前K個(gè)元素。正常的思路是先將數(shù)組排序，然后找到前K個(gè)元素，但這樣做通常會(huì)面臨時(shí)間復(fù)雜度、空間復(fù)雜度雙雙過(guò)高的問(wèn)題。如果面試官問(wèn)你，這堆數(shù)據(jù)有好幾百G，甚至上T，你怎么辦？

? 所以，我們就得想其他辦法來(lái)解決這個(gè)問(wèn)題。一個(gè)思路是，利用哈希表的思想來(lái)解題，如計(jì)數(shù)排序等。還有一個(gè)思路是利用堆排序來(lái)解題，這是比較常用的方法。

? 整體思路就是，先遍歷整個(gè)數(shù)組，將滿足要求的元素放入堆中，維持堆的大小為K；當(dāng)遍歷結(jié)束的時(shí)候，堆就是題目要求的前K個(gè)元素。

??

分析：

? 求前K大元素用小根堆來(lái)解答，這題需要先用一個(gè)哈希表來(lái)計(jì)算每個(gè)元素的頻率，然后再用小根堆來(lái)求頻率最高的前K個(gè)元素。

? 需要注意的是，c++的優(yōu)先隊(duì)列容器默認(rèn)是大根堆。

分析：

? 這題的關(guān)鍵點(diǎn)在于當(dāng)出現(xiàn)的頻率相同時(shí)，需要按照字母順序排序，最簡(jiǎn)單的做法是按照老方法：

1. 先用哈希表計(jì)算單詞頻率

2. 再用小根堆存儲(chǔ)前K高頻單詞，并同時(shí)判斷頻率是否相等，來(lái)安排單詞順序

3. 將小根堆存儲(chǔ)到數(shù)組中

? 這里需要用到c++的operator方法，來(lái)重載優(yōu)先隊(duì)列容器，使小根堆在存儲(chǔ)元素的同時(shí)，也比較單詞的字母大小。注意小根堆最后輸出的時(shí)候要翻轉(zhuǎn)數(shù)組。