2 Java Solutions

• Solution 1. Bucket Sort

``````class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
List<Integer> res = new ArrayList<>();
if (nums == null || nums.length == 0 || k <= 0) return res;
int n = nums.length;
Map<Integer, Integer> hist = new HashMap<>();
for (int num : nums) {
hist.put(num, hist.getOrDefault(num, 0) + 1);
}

if (k >= hist.size()) return new ArrayList<Integer>(hist.keySet());
List<Integer>[] bucket = new List[n + 1];
for (int num : hist.keySet()) {
int cnt = hist.get(num);
if (bucket[cnt] == null) bucket[cnt] = new ArrayList<Integer>();
}
for (int i = n; i >= 0 && res.size() < k; --i) {
if (bucket[i] != null && bucket[i].size() > 0) {
while (res.size() > k) {
res.remove(res.size() - 1);
}
}
}
return res;
}
}
``````

Solution 2. Quick Select:

``````class Solution {
private class Ele {
int val;
int cnt;
public Ele(int val, int cnt) {
this.val = val;
this.cnt = cnt;
}
}
public List<Integer> topKFrequent(int[] nums, int k) {
List<Integer> res = new ArrayList<>();
if (nums == null || k <= 0) return res;
int n = nums.length;
Map<Integer, Integer> hist = new HashMap<>();
for (int num : nums) hist.put(num, hist.getOrDefault(num, 0) + 1);
if (k >= hist.size()) return new ArrayList<Integer>(hist.keySet());
Ele[] arr = new Ele[hist.size()];
int ind = 0;
for (int num : hist.keySet()) {
arr[ind++] = new Ele(num, hist.get(num));
}

int lo = 0, hi = hist.size() - 1;
while (lo < hi) {
int p = partition(arr, lo, hi);
if (p == k - 1) break;
if (p < k - 1) {
lo = p + 1;
} else {
hi = p - 1;
}
}
for (int i = 0; i < k; ++i) {
}
return res;
}
private int partition(Ele[] arr, int lo, int hi) {
int pivot = arr[hi].cnt;
int i = lo - 1;
for (int j = lo; j < hi; ++j) {
if (arr[j].cnt > pivot) {
swap(arr, ++i, j);
}
}
swap(arr, ++i, hi);
return i;
}
private void swap(Ele[] arr, int i, int j) {
if (i == j) return;
Ele temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.