347TopKFrequentElements.org

347 Top K Frequent Elements - LeetCode

思路：用一个 Map 统计元素出现的频率，通过小顶堆来实现排序，当堆的容量达到 k 时，移除堆顶元素，从而保证堆的里元素出现的频率都是排在 k 以后。

题目

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.
• 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.

Java

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num,0) + 1);
        }
        PriorityQueue<Integer> pq = new PriorityQueue((n1, n2) -> freq.get(n1) - freq.get(n2));
        for (int num : freq.keySet()) {
            pq.offer(num);
            if (pq.size() > k) {
                pq.poll();
            }
        }
     
        int size = pq.size();
     
        int[] res = new int[size];
        for (int i = 0; i < size; i++) {
            res[i] = pq.poll();
        }
        return res;
     
    }
}

CPP

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
     
        unordered_map<int, int> freq;
        for (int i = 0; i < nums.size(); i++){
            freq[nums[i]]++;
        }
     
        priority_queue<pair<int, int> , vector<pair<int, int>>, greater<pair<int, int>> > pq;
     
        for (unordered_map<int, int>::iterator iter = freq.begin(); iter != freq.end(); iter++) {
            if (pq.size() == k) {
                // map 中第二个是出现的频率，pq 中第一个是频率
                if (iter->second > pq.top().first) {
                    pq.pop();
                    pq.push(make_pair(iter->second, iter->first));
                }
            }else {
                pq.push(make_pair(iter->second, iter->first));
            }
        }
     
        vector<int> res;
        while (!pq.empty()) {
            res.push_back(pq.top().second);
            pq.pop();
        }
     
        return res;
    }
 
 
};

CPP优化

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {

        unordered_map<int, int> freq;
        for (int i = 0; i < nums.size(); i++){
            freq[nums[i]]++;
        }

        priority_queue<pair<int, int> , vector<pair<int, int>>, greater<pair<int, int>> > pq;

        for (unordered_map<int, int>::iterator iter = freq.begin(); iter != freq.end(); iter++) {
            // 超过 k 的时候移除堆顶
            pq.push(make_pair(iter->second, iter->first));
            if (pq.size() > k) {
                pq.pop();
            }
        }

        vector<int> res;
        while (!pq.empty()) {
            res.push_back(pq.top().second);
            pq.pop();
        }

        return res;
    }


};