資訊專欄INFORMATION COLUMN
摘要：先按照元素次數(shù)的將所有元素存入，再按照次數(shù)元素將哈希表里的所有元素存入，然后取最后的個(gè)元素返回。
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.
先按照元素-次數(shù)的pair將所有元素存入HashMap，再按照次數(shù)-元素pair將哈希表里的所有元素存入TreeMap，然后取TreeMap最后的k個(gè)元素返回。
public class Solution {
public List topKFrequent(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;
}
}
Min Heap
lambda-expression
public class Solution {
public List topKFrequent(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;
}
}
no-lambda
public class Solution {
public List topKFrequent(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;
}
}
Max Heap
public class Solution {
public List topKFrequent(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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66124.html
摘要：描述給定一個(gè)非空的整數(shù)數(shù)組，返回其中出現(xiàn)頻率前高的元素。然后以元素出現(xiàn)的次數(shù)為值，統(tǒng)計(jì)該次數(shù)下出現(xiàn)的所有的元素。從最大次數(shù)遍歷到次，若該次數(shù)下有元素出現(xiàn)，提取該次數(shù)下的所有元素到結(jié)果數(shù)組中，知道提取到個(gè)元素為止。 Description Given a non-empty array of integers, return the k most frequent elements. E...
摘要：題目要求假設(shè)有一個(gè)非空的整數(shù)數(shù)組，從中獲得前個(gè)出現(xiàn)頻率最多的數(shù)字。先用來(lái)統(tǒng)計(jì)出現(xiàn)次數(shù)，然后將其丟到對(duì)應(yīng)的桶中，最后從最高的桶開(kāi)始向低的桶逐個(gè)遍歷，取出前個(gè)頻率的數(shù)字。 題目要求 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...
摘要：例如題目解析題目的意思很明顯，就是把兩個(gè)數(shù)字加起來(lái)，需要考慮進(jìn)位的情況?？偨Y(jié)這個(gè)題目如果都能獨(dú)立完成，那么水平已經(jīng)可以足以應(yīng)付國(guó)內(nèi)各大企業(yè)的算法面。 歡迎大家前往騰訊云+社區(qū)，獲取更多騰訊海量技術(shù)實(shí)踐干貨哦~ 本文由落影發(fā)表 前言 LeetCode上的題目是大公司面試常見(jiàn)的算法題，今天的目標(biāo)是拿下5道算法題： 題目1是基于鏈表的大數(shù)加法，既考察基本數(shù)據(jù)結(jié)構(gòu)的了解，又考察在處理加法過(guò)程中...
閱讀 1367·2021-11-15 11:45
閱讀 3134·2021-09-27 13:36
閱讀 2878·2019-08-30 15:54
閱讀 995·2019-08-29 12:38
閱讀 2915·2019-08-29 11:22
閱讀 2997·2019-08-26 13:52
閱讀 2042·2019-08-26 13:30
閱讀 595·2019-08-26 10:37
