347. Top K Frequent Elements

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

Given a non-empty array of integers, return the k most frequent elements.

For example,

Given [1,1,1,2,2,3] and k = 2, return [1,2].

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.

Thoughts

找出现频率最高的K个元素。前x的k个=>heap。要求最大的k个，维持一个大小为k的min heap，每次遍历时当超过k个时，把最小的踢出去，剩下的的就是最大的K个。

Code

/*
 * @lc app=leetcode id=347 lang=cpp
 *
 * [347] Top K Frequent Elements
 */

// @lc code=start
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        const auto cmp = [](auto &a, auto &b) {
            return a.first > b.first;
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
        for (const auto num : nums) ++freq[num];
        for (const auto &p : freq) {
            pq.push({p.second, p.first});
            if (pq.size() > k) {
                pq.pop();
            }
        }
        vector<int> res(k, 0);
        for (int i = k - 1; i >= 0; --i) {
            res[i] = pq.top().second;
            pq.pop(); 
        }
        return res;
    }
};
// @lc code=end

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], 1);
            } else {
                map.put(nums[i], map.get(nums[i]) + 1);
            }
        }

        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(
            new Comparator<Map.Entry<Integer, Integer>>() {
                @Override
                public int compare(Map.Entry<Integer, Integer> a, Map.Entry<Integer, Integer> b) {
                    return a.getValue() - b.getValue();
                }
            }
        );

        for (Map.Entry e : map.entrySet()) {
            pq.add(e);
            if (pq.size() > k) {
                pq.poll();
            }
        }

        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < k; ++i) {
            Map.Entry e = pq.poll();
            res.add(0, (int)e.getKey());
        }

        return res;
    }
}

Analysis

时间复杂度O(n + klgn).