MENU

LeetCode347. Top K Frequent Elements(模拟)

2019 年 04 月 17 日 • 阅读: 828 • LeetCode阅读设置

LeetCode347. Top K Frequent Elements(模拟)

  • Medium
  • Accepted:191,936
  • Submissions:354,049

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(nlogn)$, where n is the array's size.

链接

https://leetcode.com/problems/top-k-frequent-elements

题意

给定一个非空数组,求出现最频繁的k个元素。

题解

统计每个元素出现的次数,然后按照出现的次数排序,取前k个就好了,实现方式有很多。

我是用unordered_map统计每个元素出现的次数,然后用优先队列排序,时间复杂度$O(nlog(n-k))$,n-k是因为优先队列中最多存放n-k个元素。

代码

Time SubmittedStatusRuntimeMemoryLanguage
5 hours agoAccepted20 ms11.4 MBcpp
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector <int> ret;
        unordered_map <int, int> umap;
        int n = nums.size();
        for (int i = 0; i < n; ++i)
            umap[nums[i]]++;
        priority_queue<pair<int, int> > pq;
        for (auto it = umap.begin(); it != umap.end(); ++it)
        {
            pq.push(make_pair(it->second, it->first));
            if (pq.size() > umap.size() - k)
            {
                ret.push_back(pq.top().second);
                pq.pop();
            }
        }
        return ret;
    }
};

The end.
2019年4月17日 星期三