資訊專(zhuān)欄INFORMATION COLUMN
Problem
Given a non-empty array of integers, return the k most frequent elements.
ExampleGiven [1,1,1,2,2,3] and k = 2, return [1,2].
NoteYou 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.
public class Solution {
public List topKFrequent(int[] nums, int k) {
int n = nums.length;
Map map = new HashMap<>();
for (int num: nums) {
if (map.containsKey(num)) map.put(num, map.get(num)+1);
else map.put(num, 1);
}
List[] freq = new ArrayList[n+1];
for (int num : map.keySet()) {
int i = map.get(num);
if (freq[i] == null) {
freq[i] = new ArrayList<>();
}
freq[i].add(num);
}
List res = new ArrayList<>();
for (int index = freq.length - 1; index >= 0 && res.size() < k; index--) {
if (freq[index] != null) {
res.addAll(freq[index]);
}
}
return res;
}
}
Update 2018-9
PriorityQueue
class Solution {
public List topKFrequent(int[] nums, int k) {
List res = new ArrayList<>();
if (nums == null || nums.length < k) return res;
Map map = new HashMap<>();
PriorityQueue> queue = new PriorityQueue<>((a, b)->b.getValue()-a.getValue());
for (int num: nums) {
map.put(num, map.getOrDefault(num, 0)+1);
}
for (Map.Entry entry: map.entrySet()) {
queue.offer(entry);
}
int count = 0;
while (count < k) {
Map.Entry entry = queue.poll();
res.add(entry.getKey());
count++;
}
return res;
}
}
Bucket sort
class Solution {
public List topKFrequent(int[] nums, int k) {
List res = new ArrayList<>();
if (nums == null || nums.length < k) return res;
Map map = new HashMap<>();
for (int num: nums) {
map.put(num, map.getOrDefault(num, 0)+1);
}
List[] buckets = new ArrayList[nums.length+1];
for (Map.Entry entry: map.entrySet()) {
int value = entry.getValue();
if (buckets[value] == null) buckets[value] = new ArrayList<>();
buckets[value].add(entry.getKey());
}
for (int i = buckets.length-1; i >= 0 && res.size() < k; i--) {
if (buckets[i] != null) res.addAll(buckets[i]);
}
return res;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65995.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,...
摘要：先按照元素次數(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: ...
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ò)程中...
閱讀 892·2021-11-15 11:38
閱讀 1619·2021-09-24 09:48
閱讀 851·2021-09-24 09:47
閱讀 2281·2021-08-26 14:15
閱讀 3512·2019-08-30 11:09
閱讀 2616·2019-08-29 16:55
閱讀 1593·2019-08-26 14:01
閱讀 3047·2019-08-23 16:47
