LeetCode 347 Top K Frequent Elements (HashMap TreeMap 或 PriorityQueue 推荐)

本文主要是介绍LeetCode 347 Top K Frequent Elements (HashMap TreeMap 或 PriorityQueue 推荐)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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.

题目链接：https://leetcode.com/problems/top-k-frequent-elements/

题目分析：O(n)可以用桶排，这里直接给出TreeMap和优先队列的做法(主要是mark下java集合的一些用法)

TreeMap：击败85%

getOrDefault是Java 8的新方法

public class Solution {public List<Integer> topKFrequent(int[] nums, int k) {HashMap<Integer, Integer> mp = new HashMap<>();for (int val: nums) {mp.put(val, mp.getOrDefault(val, 0) + 1);}TreeMap<Integer, List<Integer>> freqMap = new TreeMap<>();for (int val: mp.keySet()) {int cur = mp.get(val);if (!freqMap.containsKey(cur)) {freqMap.put(cur, new ArrayList<>());}freqMap.get(cur).add(val);}List<Integer> ans = new ArrayList<>();while (ans.size() < k) {Map.Entry<Integer, List<Integer>> entry = freqMap.pollLastEntry();ans.addAll(entry.getValue());}return ans;}
}

优先队列：击败18%

public class Solution {public List<Integer> topKFrequent(int[] nums, int k) {HashMap<Integer, Integer> mp = new HashMap<>();for (int val: nums) {mp.put(val, mp.getOrDefault(val, 0) + 1);}PriorityQueue<Map.Entry<Integer, Integer>> q = new PriorityQueue<>((a, b) -> (b.getValue() - a.getValue()));for (Map.Entry<Integer, Integer> entry : mp.entrySet()) {q.add(entry);}List<Integer> ans = new ArrayList<>();while (ans.size() < k) {Map.Entry<Integer, Integer> entry = q.poll();ans.add(entry.getKey());}return ans;}
}

这篇关于LeetCode 347 Top K Frequent Elements (HashMap TreeMap 或 PriorityQueue 推荐)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---