# Java O(n) solution using hash map and quickselect

• public class Solution {

``````private ArrayList<Integer> res = new ArrayList<Integer>();

public List<Integer> topKFrequent(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
ArrayList<Integer> uniqueNums = new ArrayList<Integer>();

// construct the map of <number, frequency>
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
map.put(nums[i], map.get(nums[i])+1);
} else {
map.put(nums[i], 1);
}
}

// find top k frequent number from uniqueNums list according to their freq in map
return findTopKFrequent(uniqueNums, map, k, 0, uniqueNums.size()-1);
}

/* quickSelect
*/
private ArrayList<Integer> findTopKFrequent(ArrayList<Integer> uniqueNums, HashMap<Integer, Integer> map, int k, int start, int end) {

if (k == 0) return res;

int left = start, pivot = map.get(uniqueNums.get(end));

for (int i = start; i < end; i++) {
if (map.get(uniqueNums.get(i)) > pivot) {
Collections.swap(uniqueNums, i, left);
left++;
}
}
Collections.swap(uniqueNums, left, end);

if (left - start + 1 > k) return findTopKFrequent(uniqueNums, map, k, start, left - 1);
else {
for (int j = start; j < left + 1; j++) {