这篇文章主要介绍了Java实现TopK问题的方法，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧
面试中会经常遇到手撕代码的情况，而求TopK的是经常遇到的题目。下面我就用Java来实现。主要通过两种方法实现，快排思想以及堆排序的思想，两者的复杂度为O（NlogK）。
基于快排的TopK实现：
import java.util.Arrays; /** * 使用快排实现的TopK问题 Title: Description: Company: * * @author 郑伟 * @date 2018年4月10日下午9:28:15 */ public class TopK_PartitionSort { public static void main(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)); } public static void partitionSort(int[] nums, int low, int high, int K) { if (low = nums[low]) { ++low; } // 找到比pivotkey大的书了，那就交换 temp = nums[low]; nums[low] = nums[high]; nums[high] = temp; // 这时，pivotkey对应于nums[low] } return low;// 返回pivotkey对应的正确位置 } } 其实整个代码和快排一样，就是多了一个下标位置的判断，if (K - 1 == pointKey)，这是核心，也就是为什么复杂度为NlogK。如果看不懂，可以先去理解快排的实现。
堆排序实现TopK：
/** * 使用堆排序实现的TopK问题 Title: Description: Company: * * @author 郑伟 * @date 2018年4月11日上午9:28:15 */ public class TopK_HeapSort { public static void main(String[] args) { int[] num = { 2, 20, 3, 7, 9, 1, 17, 18, 0, 4 }; heapSort(num,3); System.out.println(Arrays.toString(num)); } /** * 堆排序 * * @param num */ private static void heapSort(int[] num, int K) { for (int i = num.length / 2 - 1; i >= 0; i--) { adjustMin(num, i, num.length);// 调整0~num.length-1的数据 } // 如果要实现topK，就在这里执行 for (int j = 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 } /** * 交换栈顶和最后一个元素 * * @param num * @param i * @param j */ private static void swap(int[] num, int i, int j) { int tem = num[i]; num[i] = num[j]; num[j] = tem; } /** * 调整为大顶堆 * * @param num * @param root_index */ private static void adjust(int[] num, int root_index, int length) { // int root = num[root_index]; for (int j = root_index * 2 + 1; j num[k + 1]) k = k + 1;// K指向最小的子节点 if (num[k] 算法核心思想：与一般的堆排序不同的是，TopK只需要堆尾与堆顶交换K次就好，不需要全部交换一遍。
以上就是Java实现TopK问题的方法的详细内容，更多请关注0133技术站其它相关文章！
