Java实现TopK问题的方法
面试中会经常遇到手撕代码的情况，而求TopK的是经常遇到的题目。下面我就用Java来实现。主要通过两种方法实现，快排思想以及堆排序的思想，两者的复杂度为O（NlogK）。
基于快排的TopK实现：
importjava.util.Arrays;
/**
*使用快排实现的TopK问题Title:Description:Company:
*
*@author郑伟
*@date2018年4月10日下午9:28:15
*/
publicclassTopK_PartitionSort{
publicstaticvoidmain(String[]args){
int[]num={2,20,3,7,9,1,17,18,0,4};
partitionSort(num,0,num.length-1,3);
System.out.println(Arrays.toString(num));
}
publicstaticvoidpartitionSort(int[]nums,intlow,inthigh,intK){
if(low=nums[low]){
++low;
}
//找到比pivotkey大的书了，那就交换
temp=nums[low];
nums[low]=nums[high];
nums[high]=temp;
//这时，pivotkey对应于nums[low]
}
returnlow;//返回pivotkey对应的正确位置
}
}
其实整个代码和快排一样，就是多了一个下标位置的判断，if(K-1==pointKey)，这是核心，也就是为什么复杂度为NlogK。如果看不懂，可以先去理解快排的实现。
堆排序实现TopK：
/**
*使用堆排序实现的TopK问题Title:Description:Company:
*
*@author郑伟
*@date2018年4月11日上午9:28:15
*/
publicclassTopK_HeapSort{
publicstaticvoidmain(String[]args){
int[]num={2,20,3,7,9,1,17,18,0,4};
heapSort(num,3);
System.out.println(Arrays.toString(num));
}
/**
*堆排序
*
*@paramnum
*/
privatestaticvoidheapSort(int[]num,intK){
for(inti=num.length/2-1;i>=0;i--){
adjustMin(num,i,num.length);//调整0~num.length-1的数据
}
//如果要实现topK，就在这里执行
for(intj=num.length-1;j>=0&&K>0;j--,K--){
//交换最后一个
swap(num,0,j);
//再次调整0~j-1的数据
adjustMin(num,0,j);
}
//使用最大堆，K=3，输出[9,7,3,2,4,1,0,17,18,20]，最大的三个值17,18,20
//使用最小堆，K=3，输出[3,4,9,7,20,18,17,2,1,0]，最小的三个值2,1,0
}
/**
*交换栈顶和最后一个元素
*
*@paramnum
*@parami
*@paramj
*/
privatestaticvoidswap(int[]num,inti,intj){
inttem=num[i];
num[i]=num[j];
num[j]=tem;
}
/**
*调整为大顶堆
*
*@paramnum
*@paramroot_index
*/
privatestaticvoidadjust(int[]num,introot_index,intlength){
//
introot=num[root_index];
for(intj=root_index*2+1;jnum[k+1])
k=k+1;//K指向最小的子节点
if(num[k]
算法核心思想：与一般的堆排序不同的是，TopK只需要堆尾与堆顶交换K次就好，不需要全部交换一遍。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。