347. Top K Frequent Elements
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.
Solutions:
public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
HashMap<Integer, Integer> count = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i ++) {
if (!count.containsKey(nums[i])) {
count.put(nums[i], 0);
}
count.put(nums[i], count.get(nums[i]) + 1);
}
HashMap<Integer, Queue<Integer>> reverse = new HashMap<Integer, Queue<Integer>>();
PriorityQueue<Integer> app = new PriorityQueue<Integer>(k, Collections.reverseOrder());
for (Integer i:count.keySet()) {
int val = count.get(i);
app.add(val);
if (!reverse.containsKey(val)){
reverse.put(val, new LinkedList());
}
reverse.get(val).add(i);
}
List<Integer> result = new LinkedList<Integer>();
for (int i = 0; i < k; i ++) {
int val = app.poll();
result.add(reverse.get(val).poll());
}
return result;
}
}
public class Solution {
private class Count {
public int num;
public int count;
public Count(int num, int count) {
this.num = num;
this.count = count;
}
}
private class CountComparator implements Comparator<Count> {
public int compare(Count c1, Count c2) {
return c1.count - c2.count;
}
}
public List<Integer> topKFrequent(int[] nums, int k) {
HashMap<Integer, Integer> count = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i ++) {
if (!count.containsKey(nums[i])) {
count.put(nums[i], 0);
}
count.put(nums[i], count.get(nums[i]) + 1);
}
PriorityQueue<Count> app = new PriorityQueue<Count>(k + 1, new CountComparator());
for (Integer i:count.keySet()) {
int val = count.get(i);
app.add(new Count(i, val));
if (app.size() > k) {
app.poll();
}
}
List<Integer> result = new LinkedList<Integer>();
for (int i = 0; i < k; i ++) {
int num = app.poll().num;
result.add(0, num);
}
return result;
}
}
public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
HashMap<Integer, Integer> count = new HashMap<Integer, Integer>();
int max = 0;
for (int i = 0; i < nums.length; i ++) {
if (!count.containsKey(nums[i])) {
count.put(nums[i], 0);
}
int c = count.get(nums[i]) + 1;
max = Math.max(max, c);
count.put(nums[i], c);
}
LinkedList<Integer>[] bucket = (LinkedList<Integer>[]) new LinkedList[max+1];
for (Integer i:count.keySet()) {
int val = count.get(i);
if (bucket[val] == null) {
bucket[val] = new LinkedList<Integer>();
}
bucket[val].add(i);
}
List<Integer> result = new LinkedList<Integer>();
for (int i = 0; i < k; i ++) {
while(bucket[max] == null || bucket[max].size() == 0) {
max --;
}
result.add(bucket[max].poll());
}
return result;
}
}