[leetcode]347. Top K Frequent Elements

Given a non-empty array of integers, return the?k?most frequent elements.

For example,
Given?[1,1,1,2,2,3]?and k = 2, return?[1,2].

Note:?

You may assume?k?is always valid, 1 ≤?k?≤ number of unique elements.
Your algorithm's time complexity?must be?better than O(n?log?n), where?n?is the array's size.

Subscribe?to see which companies asked this question

Solution:

1.使用hashtable獲取每個元素出現的次數

2.使用小根堆heap排序（priority queue實現），獲取前K個出現次數最多的元素pair

3.輸出，注意是小根堆，要reverse一下

時間復雜度：O(N * logK)

 1 class CompareDist
 2 {
 3 public:
 4     bool operator()(pair<int, int> n1, pair<int, int> n2) 
 5     {
 6         return n1.second > n2.second;
 7     }
 8 };
 9 
10 class Solution {
11 public:
12     vector<int> topKFrequent(vector<int>& nums, int k) 
13     {
14         vector<int> ret;
15         unordered_map<int, int> htable;
16         
17         for (int key : nums) // get each key appears times
18             htable[key]++;
19 
20         priority_queue<pair<int, int>, vector<pair<int, int> >, CompareDist> sheap; // use min heap to get k biggest
21         for (auto elem : htable)
22         {
23             if (sheap.size() < k)
24             {
25                 sheap.push(elem);
26             }
27             else
28             {
29                 pair<int, int> heap_min = sheap.top();
30                 if (elem.second > heap_min.second)
31                 {
32                     sheap.pop();
33                     sheap.push(elem);
34                 }
35             }
36         }
37         
38         while (!sheap.empty())
39         {
40             pair<int, int> heap_min = sheap.top();
41             ret.push_back(heap_min.first);
42             sheap.pop();
43         }
44         reverse(ret.begin(), ret.end());
45         
46         return ret;
47     }
48 };

或者直接使用make_heap操作，時間復雜度O(N + KlogN) = O(N)

 1 vector<int> topKFrequent(vector<int>& nums, int k) 
 2     {
 3         unordered_map<int, int> htable;
 4         for (auto &n : nums) 
 5             htable[n]++;
 6 
 7         vector<pair<int, int>> heap;
 8         for (auto &i : htable) 
 9             heap.push_back({i.second, i.first});
10 
11         vector<int> result;
12         make_heap(heap.begin(), heap.end());
13         while (k--) 
14         {
15             result.push_back(heap.front().second);
16             pop_heap(heap.begin(), heap.end());
17             heap.pop_back();
18         }
19         return result;
20     }

轉載于:https://www.cnblogs.com/ym65536/p/5537052.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/287560.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/287560.shtml
英文地址，請注明出處：http://en.pswp.cn/news/287560.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！