347. Top K Frequent Elements

川长思鸟来 2022-03-22 03:34 348阅读 0赞

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

Example 1:

  1. Input: nums = [1,1,1,2,2,3], k = 2
  2. Output: [1,2]

Example 2:

  1. Input: nums = [1], k = 1
  2. Output: [1]

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.

解法：统计前K个高频数字。考虑用HashMap来做，建立数字和其出现次数的映射，然后再按照出现次数进行堆排序。在C++中使用priority_queue来实现，默认是最大堆。

  1. class Solution {
  2. public:
  3.       vector<int> topKFrequent(vector<int>& nums, int k) {
  4.     unordered_map<int, int> maps;
  5.     priority_queue<pair<int, int>> que;
  6.     vector<int> res;
  7.     for (auto num : nums) 
  8.         ++maps[num];
  9.     for (auto iter : maps)
  10.         que.push({ iter.second, iter.first });
  11.     for (int i = 0; i < k; ++i) {
  12.         res.push_back(que.top().second);
  13.         que.pop();
  14.     }
  15.     return res;
  16.  }
  17. };

发表评论

表情：
评论列表 （有 0 条评论，348人围观）

还没有评论，来说两句吧...

相关阅读