leetcode 347. Top K Frequent Elements
本帖最后由 Seawolf 于 2019-9-10 03:40 编辑Given a non-empty array of integers, return the k most frequent elements.
Example 1:
Input: nums = , k = 2
Output:
Example 2:
Input: nums = , k = 1
Output:
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.
using regular hashmap!
import java.util.Collection;
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
List<Integer> list = new ArrayList<>();
HashMap <Integer,Integer> map = new HashMap<>();
for(int i = 0; i< nums.length; i++){
map.put(nums, map.getOrDefault(nums,0)+1);
}
Collection<Integer> c = map.values();
Object[] obj = c.toArray();
Arrays.sort(obj);
int i = 0;
while(k-- != 0){
for(Integer key : map.keySet()){
if (map.get(key).equals(Integer.parseInt(obj.toString())))
{
i++;
list.add(key);
map.remove(key);
break;
}
}
}
return list;
}
}
using bucket sort!!
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
for(int a : nums) map.put(a,map.getOrDefault(a,0)+1);
List<Integer> [] bucket = new List;
for(Integer key : map.keySet()){
int fre = map.get(key);
if(bucket == null) bucket = new ArrayList<>();
bucket.add(key);
}
List<Integer> re = new ArrayList<>();
for(int i = bucket.length - 1; i >=0 && re.size() < k ; i--){
if(bucket != null) re.addAll(bucket);
}
return re;
}
}
using java heap!
import java.util.*;
class Solution {
class Pair{
int num;
int count;
public Pair(int num, int count){
this.num = num;
this.count =count;
}
}
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for(int a: nums) map.put(a,map.getOrDefault(a,0)+1);
PriorityQueue<Pair> queue = new PriorityQueue<Pair>(new Comparator<Pair>(){
public int compare(Pair a, Pair b){
return a.count- b.count;
}
});
for(Map.Entry<Integer,Integer> entry: map.entrySet()){
Pair p = new Pair(entry.getKey(), entry.getValue());
queue.offer(p);
if(queue.size() > k) queue.poll();
}
List<Integer> list = new ArrayList<>();
while(queue.size()>0) list.add(queue.poll().num);
Collections.reverse(list);
return list;
}
}
页:
[1]