摘要:先按照元素次数的将所有元素存入,再按照次数元素将哈希表里的所有元素存入,然后取最后的个元素返回。
Problem
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.
Store each nums element and its count in HashMap.
Traverse its keySet(), store the count of each key into TreeMap, which means reverse the key-value pairs. And TreeMap will sort the elements by count value.
Use pollLastEntry() to get last K entries from TreeMap; then addAll() to put values in ArrayList res.
先按照元素-次数的pair将所有元素存入HashMap,再按照次数-元素pair将哈希表里的所有元素存入TreeMap,然后取TreeMap最后的k个元素返回。
public class Solution { public ListMin Heap lambda-expressiontopKFrequent(int[] nums, int k) { Map map = new HashMap<>(); for (int num: nums) { map.put(num, map.getOrDefault(num, 0)+1); } TreeMap > sorted = new TreeMap<>(); for (int num: map.keySet()) { int count = map.get(num); if (!sorted.containsKey(count)) sorted.put(count, new LinkedList<>()); sorted.get(count).add(num); } List res = new ArrayList<>(); while (res.size() < k) { Map.Entry > entry = sorted.pollLastEntry(); res.addAll(entry.getValue()); } return res; } }
public class Solution { public Listno-lambdatopKFrequent(int[] nums, int k) { List res = new ArrayList<>(); if (nums.length < k) return res; Map map = new HashMap<>(); for (int num: nums) { map.put(num, map.getOrDefault(num, 0)+1); } PriorityQueue > minHeap = new PriorityQueue<>((a, b)->(a.getValue()-b.getValue())); for (Map.Entry entry: map.entrySet()) { minHeap.offer(entry); if (minHeap.size() > k) minHeap.poll(); } while (res.size() < k) { res.add(minHeap.poll().getKey()); } return res; } }
public class Solution { public ListMax HeaptopKFrequent(int[] nums, int k) { List res = new ArrayList<>(); if (nums.length < k) return res; Map map = new HashMap<>(); for (int num: nums) { map.put(num, map.getOrDefault(num, 0)+1); } PriorityQueue > minHeap = new PriorityQueue >(new Comparator >() { public int compare(Map.Entry a, Map.Entry b) { return a.getValue()-b.getValue(); } }); for (Map.Entry entry: map.entrySet()) { minHeap.offer(entry); if (minHeap.size() > k) minHeap.poll(); } while (res.size() < k) { Map.Entry entry = minHeap.poll(); res.add(entry.getKey()); } return res; } }
public class Solution { public ListtopKFrequent(int[] nums, int k) { List res = new ArrayList<>(); if (nums.length < k) return res; Map map = new HashMap<>(); for (int num: nums) { map.put(num, map.getOrDefault(num, 0)+1); } PriorityQueue > maxHeap = new PriorityQueue<>((a, b) -> (b.getValue()-a.getValue())); for (Map.Entry entry: map.entrySet()) { maxHeap.offer(entry); } while (res.size() < k) { res.add(maxHeap.poll().getKey()); } return res; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/66124.html
摘要:描述给定一个非空的整数数组,返回其中出现频率前高的元素。然后以元素出现的次数为值,统计该次数下出现的所有的元素。从最大次数遍历到次,若该次数下有元素出现,提取该次数下的所有元素到结果数组中,知道提取到个元素为止。 Description Given a non-empty array of integers, return the k most frequent elements. E...
摘要:题目要求假设有一个非空的整数数组,从中获得前个出现频率最多的数字。先用来统计出现次数,然后将其丢到对应的桶中,最后从最高的桶开始向低的桶逐个遍历,取出前个频率的数字。 题目要求 Given a non-empty array of integers, return the k most frequent elements. For example, Given [1,1,1,2,2,...
Problem Given a non-empty array of integers, return the k most frequent elements. 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 e...
LeetCode version Problem Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, t...
摘要:例如题目解析题目的意思很明显,就是把两个数字加起来,需要考虑进位的情况。总结这个题目如果都能独立完成,那么水平已经可以足以应付国内各大企业的算法面。 欢迎大家前往腾讯云+社区,获取更多腾讯海量技术实践干货哦~ 本文由落影发表 前言 LeetCode上的题目是大公司面试常见的算法题,今天的目标是拿下5道算法题: 题目1是基于链表的大数加法,既考察基本数据结构的了解,又考察在处理加法过程中...
阅读 1323·2021-11-15 11:45
阅读 3095·2021-09-27 13:36
阅读 2814·2019-08-30 15:54
阅读 960·2019-08-29 12:38
阅读 2855·2019-08-29 11:22
阅读 2954·2019-08-26 13:52
阅读 1992·2019-08-26 13:30
阅读 528·2019-08-26 10:37