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);
if (!reverse.containsKey(val)){
}
}
for (int i = 0; i < k; i ++) {
int val = app.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);
if (app.size() > k) {
app.poll();
}
}
for (int i = 0; i < k; i ++) {
int num = app.poll().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);
}
for (Integer i:count.keySet()) {
int val = count.get(i);
if (bucket[val] == null) {
}
}
for (int i = 0; i < k; i ++) {
while(bucket[max] == null || bucket[max].size() == 0) {
max --;
}