# Average O(n) based on quickselect

• ``````public class Solution {
public static class Element {
int freq;
int val;
public Element(int val, int freq) {
this.val = val;
this.freq = freq;
}
}
public List<Integer> topKFrequent(int[] nums, int k) {
Element[] elements = initElementArray(nums);
int end = quickselect(elements,0,elements.length - 1, k);
List<Integer> res = new ArrayList<>();
for(int i = 0; i <= end; i++) {
}
return res;
}
private Element[] initElementArray(int[] nums) {
Map<Integer,Integer> countMap = new HashMap<>();
for(int num : nums) {
Integer count = countMap.get(num);
if (count == null) {
countMap.put(num,1);
} else {
countMap.put(num, count + 1);
}
}
Element[] es = new Element[countMap.size()];
int i = 0;
for(Map.Entry<Integer,Integer> entry : countMap.entrySet()) {
int val = entry.getKey(), freq = entry.getValue();
es[i++] = new Element(val,freq);
}
return es;
}

private void swap(Element[] es, int i, int j) {
Element tmp = es[i];
es[i] = es[j];
es[j] = tmp;
}
private int quickselect(Element[] elements, int left, int right, int k) {
if (left > right) {
return -1;
}
int pivot = elements[right].freq;
int i = left, j = right - 1;
//xxxxxPxxxxxx
while(i <= j) {
if(elements[i].freq > pivot) {
i++;
} else {
swap(elements,i,j--);
}
}
swap(elements,i,right);
int larger = i - left + 1;
if(larger == k) {
return i;
}
if(larger > k) {
right = i - 1;
} else {
left = i + 1;
k = k - larger;
}
return quickselect(elements,left,right,k);
}
}``````

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