347.TopKFrequentElements.md

题目描述

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.

难度系数
Medium

解法一：通过一个最小值堆，堆中有k个数据，最后将k个数据输出

class Solution {
    struct cmp{
        bool operator()(pair<int, int> a,pair<int, int> b){
            return a.second>b.second;
        }
    };
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map <int, int> m;
        // pair 的第一个元素代表数组的值，第二个元素代表了该值出现的次数,最小值堆
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> min_stack;
        vector<int> res(k,0);
        for (int num: nums) m[num]++;
        //保证堆中有k个值
        for (auto it: m) {
            min_stack.push({it.first, it.second});
            if (min_stack.size() > k) min_stack.pop();
        }
        //将结果保存到vector中
        for (int i = k-1; i >= 0; i--) {
            res[i] = min_stack.top().first;
            min_stack.pop();
        }
        return res;
    }
};

解法二：原理同解法一

class Solution {
public:
    struct cmp{
        bool operator()(pair<int, int> a,pair<int, int> b){
            return a.second>b.second;
        }
    };

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> map;
        for (int v : nums)  map[v]++;

        // pair 的第一个元素代表数组的值，第二个元素代表了该值出现的次数,最小值堆
        priority_queue<pair<int, int>, vector<pair<int, int>>,cmp> min_stack;
        for (auto item : map) {
            if (min_stack.size() == k) {
                if (min_stack.top().second < item.second) {
                    min_stack.pop();
                    min_stack.push({item.first, item.second});
                }
            } else {
                min_stack.push({item.first, item.second});
            }
        }
        vector<int> ret;
        while (!min_stack.empty()) {
            ret.push_back(min_stack.top().first);
            min_stack.pop();
        }
        return ret;
    }
};