【Leetcode】347. Top K Frequent Elements（C++容器理解）（优先队列）

红太狼 2021-12-17 00:07 194阅读 0赞

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

**Example 1:**

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

**Example 2:**

Input: nums = [1], k = 1
    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个出现次数最多的数据。

解题思路：

利用map、priority\_queue和pair。

map统计每个数字出现的个数。

paiority\_queue<pair<int, int>>，在优先队列中pari的比较，先比较第一个元素，第一个相等比较第二个。

合理利用容器之间的嵌套，是C++的基本操作。

基操勿6皆坐

class Solution {
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            map<int, int> maps;
            for(int i=0;i<nums.size();i++){
                maps[nums[i]]++;
            }
            
            priority_queue<pair<int, int>> pq;
            
            for(map<int, int>::iterator it=maps.begin();it!=maps.end();it++){
                pq.push(make_pair(it->second, it->first));
            }
            
            vector<int> ans;
            for(int i=0;i<k;i++){
                auto u = pq.top();
                int top = u.second;
                ans.push_back(top);
                pq.pop();
            }
            return ans;
        }
        
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，194人围观）

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

相关阅读

相关 leetcode 347. Top K Frequent Elements | 347. 前 K 个高频元素（大根堆）

题目 [https://leetcode.com/problems/top-k-frequent-elements/][https_leetcode.com_proble

布满荆棘的人生/ 2022年08月30日 00:49/ 0 赞/ 162 阅读

相关 [leetcode]347. Top K Frequent Elements

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

冷不防/ 2022年08月22日 13:18/ 0 赞/ 151 阅读

相关 LeetCode347—Top K Frequent Elements

LeetCode347—Top K Frequent Elements 五一刚收假，状态不是很好，赶紧刷个题恢复一下技术。原题 > Given a non-em

Myth丶恋晨/ 2022年08月21日 13:39/ 0 赞/ 177 阅读

相关 [leetcode]347. Top K Frequent Elements -- JavaScript 代码

/ @param {number[]} nums @param {number} k @return {number[]} / var topKFrequ

你的名字/ 2022年07月17日 03:21/ 0 赞/ 145 阅读

相关 leetcode 347. Top K Frequent Elements

1.题目 Given a non-empty array of integers, return the k most frequent elements. 一个非空

朴灿烈づ我的快乐病毒、/ 2022年06月13日 04:55/ 0 赞/ 180 阅读

相关 leetcode 347. Top K Frequent Elements 使用HashMap计数

For example, Given \[1,1,1,2,2,3\] and k = 2, return \[1,2\]. Note: You may assume

Dear 丶/ 2022年06月07日 01:16/ 0 赞/ 161 阅读

相关 LeetCode【347】 Top K Frequent Elements

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

雨点打透心脏的1/2处/ 2022年05月11日 14:22/ 0 赞/ 151 阅读

相关 347. Top K Frequent Elements

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

川长思鸟来/ 2022年03月22日 03:34/ 0 赞/ 246 阅读

相关【Leetcode】347. Top K Frequent Elements（C++容器理解）（优先队列）

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

红太狼/ 2021年12月17日 00:07/ 0 赞/ 195 阅读

相关 LeetCode : 347. Top K Frequent Elements 根据频率选取topk元素

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

柔情只为你懂/ 2021年06月24日 16:10/ 0 赞/ 351 阅读