class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer,Integer> map=new HashMap<Integer,Integer>();
for(int n:nums){
if(map.containsKey(n)){
map.put(n,map.get(n)+1);
}else{
map.put(n,1);
}
}
List<int[]> values=new ArrayList<>();
for(Map.Entry<Integer,Integer> entry:map.entrySet()){
int num = entry.getKey(), count = entry.getValue();
values.add(new int[]{num, count});
}
int[] res=new int[k];
qsort(values,0,values.size()-1,k-1,res);
return res;
}
public void qsort(List<int[]> values,int lo,int hi,int k,int[] res){
int j=part(values,lo,hi);
if(j==k){
for(int i=0;i<=k;i++){
res[i]=values.get(i)[0];
}
return;
}else if(j<k){
qsort(values,j+1,hi,k,res);
}else{
qsort(values,lo,j-1,k,res);
}
}
public int part(List<int[]> values,int lo,int hi){
int pivot=values.get(lo)[1],l=lo-1,r=hi+1,index=lo;
while(index<r){
if(values.get(index)[1]>pivot){
Collections.swap(values,index,++l);
}
else if(values.get(index)[1]<pivot){
Collections.swap(values,index,--r);
}
else{
index++;
}
}
return index-1;
}
}
