Java怎么實現TopK問題

這篇文章主要介紹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次就好，不需要全部交換一遍。

以上是“Java怎么實現TopK問題”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注億速云行業資訊頻道！