TopK問題的Java實作

面試中會經常遇到手撕代碼的情況，而求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 = { , , , , , , , , ,  };
        partitionSort(num, , num.length - , );
        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 -  == pointKey)//TopK問題的核心，就是如果傳回的下标為K-1，說明已經排序好了K個最大/最小的數，但是之間的順序是不确定的
                return;
            partitionSort(nums, low, pointKey - , K);
            partitionSort(nums, pointKey + , 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 = { , , , , , , , , ,  };
        heapSort(num,);
        System.out.println(Arrays.toString(num));
    }

    /**
     * 堆排序
     * 
     * @param num
     */
    private static void heapSort(int[] num, int K) {
        for (int i = num.length /  - ; i >= ; i--) {
            adjustMin(num, i, num.length);// 調整0~num.length-1的資料
        }
        // 如果要實作topK，就在這裡執行
        for (int j = num.length - ; j >=  && K > ; j--,K--) {
            // 交換最後一個
            swap(num, , j);
            // 再次調整0~j-1的資料
            adjustMin(num, , 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 *  + ; j < length; j = j *  + ) {
            // 最大的兒子
            if (j +  < length && num[j] < num[j + ]) {
                j = j + ;// 指向了最大的兒子
            }
            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 *  + ; k < length; k = k *  + ) {
            if (k +  < length && num[k] > num[k + ])
                k = k + ;// K指向最小的子節點
            if (num[k] < rootValue) {
                num[root_index] = num[k];
                root_index = k;// 和k換了一下位置
            } else {
                break;// 本身不需要再調整了
            }
        }
        num[root_index] = rootValue;
    }
}
           

算法核心思想：與一般的堆排序不同的是，TopK隻需要堆尾與堆頂交換K次就好，不需要全部交換一遍。