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 < high) {
     int pointKey = partitionSortCore(nums, low, high);
     if (K - 1 == pointKey)//TopK问题的核心，就是如果返回的下标为K-1，说明已经排序好了K个最大/最小的数，但是之间的顺序是不确定的
       return;
     partitionSort(nums, low, pointKey - 1, K);
     partitionSort(nums, pointKey + 1, high, K);
   }
 }

/**
  * 快排的核心
  *
  * @param nums
  * @param low
  * @param high
  * @return 返回排序好以后的位置
  */
 public static int partitionSortCore(int[] nums, int low, int high) {
   // 以第一个座位标志位来比对
   int pivotkey = nums[low];
   while (low < high) {
     // 从pivotkey往最后一个位置比较
     while (low < high && pivotkey <= nums[high]) {
       --high;
     }
     // 开始交换pivotkey和nums[high]
     int temp = nums[low];
     nums[low] = nums[high];
     nums[high] = temp;
     // 此时nums[high]对应于pivotkey
     while (low < high && pivotkey >= 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 < length; j = j * 2 + 1) {
     // 最大的儿子
     if (j + 1 < length && num[j] < num[j + 1]) {
       j = j + 1;// 指向了最大的儿子
     }
     if (root < num[j]) {
       num[root_index] = num[j];
       root_index = j;// 标记换了哪一个位置
     } else {
       break;// 已经是大顶堆了，不需要调整了
     }
   }
   num[root_index] = root;
 }

/**
  * 小顶堆
  *
  * @param num
  * @param root_index
  * @param length
  */
 private static void adjustMin(int[] num, int root_index, int length) {
   //
   int rootValue = num[root_index];
   for (int k = root_index * 2 + 1; k < length; k = k * 2 + 1) {
     if (k + 1 < length && num[k] > num[k + 1])
       k = k + 1;// K指向最小的子节点
     if (num[k] < rootValue) {
       num[root_index] = num[k];
       root_index = k;// 和k换了一下位置
     } else {
       break;// 本身不需要再调整了
     }
   }
   num[root_index] = rootValue;
 }
}

算法核心思想：与一般的堆排序不同的是，TopK只需要堆尾与堆顶交换K次就好，不需要全部交换一遍。

来源：https://blog.csdn.net/qq_37169817/article/details/79893200