LeetCode 解题报告（100）-- 347. Top K Frequent Elements

Problem

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

Example 1:

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

Example 2:

1 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.
It’s guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
You can return the answer in any order.

Analysis

这道题目是关于数字频率统计的，这种统计常规的做法是用 map 统计。而这道题目比较难的是有一个排序，要找出出现频率前 k 个高的。既然用到排序，就是用 priority_queue，以出现的频率作为 key，以数字本身作为 value。插入到 queue 里面后，就已经排好序了，之后输出前 k 个就可以了。

Solution

直接使用 C++ 提供的 unorder_map 和 priority_queue 即可。

Code

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> m;
        priority_queue<pair<int, int>> q;
        vector<int> res;
        
        int size = nums.size ();
        
        for (int i = 0; i < size; i++) {
            m [nums [i]]++;
        }
        
        for (auto it : m) q.push ({it.second, it.first});
        for (int i = 0; i < k; ++i) {
            res.push_back (q.top ().second);
            q.pop ();
        }
        return res;
    }
};

Summary

这道题目的难度是 medium，实际的思路不难，但要求对一些数据结构的使用比较熟悉。如果对 C++ 的一些 stl 容器比较熟悉的话，这道题就能快速解决了。希望这篇博客能够帮助到您，感谢您的支持，欢迎转发、分享、评论，谢谢！