很重點(diǎn)的一道題，是劍指Offer，LeetCode里面常見的另一道題：返回?cái)?shù)組里最小/大的K個(gè)元素進(jìn)階版。

同時(shí)也是海量數(shù)據(jù)處理課里講過的一道基礎(chǔ)題，后序還有各種進(jìn)階的在線解法。

自己有思路但因?yàn)檎Z法不夠熟練，參考了討論區(qū)的解法寫的程序：涉及到了很多C++基礎(chǔ)知識(shí)，值得好好復(fù)習(xí)。

C++ STL 優(yōu)先隊(duì)列的應(yīng)用

缺點(diǎn)：最后是倒序輸出的。

class Solution { public://using value_t = pair<int, int>; //不要忘記等號(hào)typedef pair<int, int> value_t;// 因?yàn)槎阎性夭皇菢?biāo)準(zhǔn)的數(shù)據(jù)類型 && 要用最小堆，需要定義struct cmp {bool operator() (const value_t& a, const value_t& b) {return a.second > b.second;}}; //結(jié)構(gòu)體定義的分號(hào)不可少!!!vector<int> topKFrequent(vector<int>& nums, int k) {int n = nums.size();vector<int> ret;if(nums.empty()) return ret; //1-將數(shù)組轉(zhuǎn)換成哈希表unordered_map<int, int> dict;for (auto num : nums) {dict[num] ++;}//2-將哈希表存入最小堆中，將多余的元素彈出，留下的最后k項(xiàng)就是最高頻的k項(xiàng)//using value_t pair<int, int>;priority_queue<value_t, vector<value_t>, cmp> pq;for (auto a : dict) {pq.push(a);if(pq.size() > k) {pq.pop();}}//3-將堆中元素保存到數(shù)組中返回,但這樣是倒序輸出的while(!pq.empty()) {ret.push_back(pq.top().first);pq.pop();}return ret;} };

?最大堆：最后是正序輸出的，與最小堆的性能對(duì)比見末尾。

class Solution { public://using value_t = pair<int, int>; //不要忘記等號(hào)typedef pair<int, int> value_t;// 因?yàn)槎阎性夭皇菢?biāo)準(zhǔn)的數(shù)據(jù)類型 && 要用最小堆，需要定義struct cmp {bool operator() (const value_t& a, const value_t& b) {return a.second < b.second;}}; //結(jié)構(gòu)體定義的分號(hào)不可少!!!vector<int> topKFrequent(vector<int>& nums, int k) {int n = nums.size();vector<int> ret;if(nums.empty()) return ret; //1-將數(shù)組轉(zhuǎn)換成哈希表unordered_map<int, int> dict;for (auto num : nums) {dict[num] ++;}//2-將哈希表存入最大堆中//using value_t pair<int, int>;priority_queue<value_t, vector<value_t>, cmp> pq;for (auto a : dict) {pq.push(a);}//3-將堆中元素保存到數(shù)組中返回,但這樣的倒序輸出的for(int i=0; i<k; i++) {ret.push_back(pq.top().first);pq.pop();}return ret;} };

效率對(duì)比：

改用最大堆，最后結(jié)果是按照頻率逐高到低排序的，但是建堆的時(shí)間復(fù)雜度O(n)，空間也是O(n)，取k個(gè)元素是O(klogn)，

時(shí)間O(n) + O(n) + O(klogn)，空間也是O(n)。

用最小堆時(shí)間復(fù)雜度：遍歷建哈希表O(n) + 維護(hù)一個(gè)大小為k的堆O(nlogk)，空間復(fù)雜度最壞O(n) + O(k)。

總結(jié)

以上是生活随笔為你收集整理的LeetCode 347：最高频的 K 个元素的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。