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 Submitted	Status	Runtime	Memory	Language
5 hours ago	Accepted	20 ms	11.4 MB	cpp

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日星期三