347. Top K Frequent Elements

Problem:

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.

思路：

Solution (C++):

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> frequency;
    for (auto num : nums)  ++frequency[num];
    priority_queue<pair<int, int>> pri_que;
    vector<int> res;
    
    for (auto it = frequency.begin(); it != frequency.end(); ++it) {
        pri_que.push(make_pair(it->second, it->first));
        if (pri_que.size() > frequency.size() - k) {
            res.push_back(pri_que.top().second);
            pri_que.pop();
        }
    }
    return res;
}

性能：

Runtime: 24 ms  Memory Usage: 9.2 MB

思路：

Solution (C++):

性能：

Runtime: ms  Memory Usage: MB