文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 哈希
    • 2.2 優先隊列

1. 題目

給定一個非空的整數數組，返回其中出現頻率前 k 高的元素。

示例 1: 輸入: nums = [1,1,1,2,2,3], k = 2 輸出: [1,2]示例 2: 輸入: nums = [1], k = 1 輸出: [1] 說明： 你可以假設給定的 k 總是合理的，且 1 ≤ k ≤ 數組中不相同的元素的個數。 你的算法的時間復雜度必須優于 O(n log n) , n 是數組的大小。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/top-k-frequent-elements
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

2.1 哈希

class Solution { public:vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int,int> m;vector<int> ans;for(int num:nums)m[num]++;vector<pair<int,int>> v(m.begin(), m.end());//map不支持排序，轉成vectorsort(v.begin(), v.end(),[](pair<int,int> &a, pair<int,int> &b){return a.second > b.second;}); //新的比較函數寫法auto it = v.begin();while(k--){ans.push_back(it->first);++it;}return ans;} };

2.2 優先隊列

class Solution {struct cmp//必須寫struct，不能寫class{bool operator()(pair<int, int>& a, pair<int, int>& b){ return a.second > b.second; }//小頂堆}; public:vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int,int> m;vector<int> ans;for(int num:nums)m[num]++;priority_queue<pair<int,int>,vector<pair<int,int>>, cmp> q;for(auto a:m){q.push(a);if(q.size() > k)q.pop();}while(!q.empty()){ans.push_back(q.top().first);q.pop();}return ans;} };

總結

以上是生活随笔為你收集整理的LeetCode 347. 前 K 个高频元素（哈希/优先队列）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。