字節(jié)跳動面試必會：快速選擇算法，TopK問題最優(yōu)解-魔扣目錄

在面試字節(jié)跳動的過程中，現(xiàn)場寫算法代碼是繞不開的一個環(huán)節(jié)。其中快速排序(Quick Sort)、快速選擇(Quick Select)是最常見的算法題之一。快速選擇是目前解決TopK問題的最優(yōu)算法，如果想拿下字節(jié)跳動的offer，快速排序算法是必須要掌握的算法之一！

開篇先出到面試題，請讀者思考一下可能的解法：

給你一個無序數(shù)組，請找出其中第K大的數(shù)，時間復(fù)雜度控制在O(N)。

如果不對時間復(fù)雜度加約束的情況下，該題有很多種可能解法，例如：

用任意一種性能不錯的排序算法先將數(shù)組進行排序，然后從中找到位置k的數(shù)值。但即便用當(dāng)前最好的排序算法，時間復(fù)雜度也是在O(n·log n)的級別，不符合題目要求。
用大頂堆算法，僅保留K個最大的值。這種算法的時間復(fù)雜度雖然優(yōu)于前面一種，但時間復(fù)雜度也是O(n·log k)的級別，依然不滿足題目要求。

因此，為了達到題目中要求，就必須要引出今天的主角：快速選擇算法(Quick Select)。快速選擇算法是目前解決TopK問題的最優(yōu)解。其核心思想和快速排序類似，因為這兩個經(jīng)典算法的提出者都是同一個人——C.A.R.Hoare。

快速選擇的執(zhí)行步驟是先從數(shù)組中隨機選擇一個元素作為pivot，然后遍歷數(shù)組，將<pivot的元素都放在pivot左側(cè)，≥pivot的元素都放在pivot右側(cè)。如此遍歷完以后，如果要找第k大的數(shù)，可以判斷pivot兩側(cè)元素個數(shù)。假設(shè)pivot右側(cè)元素個數(shù)≥k可推斷出，第k大的數(shù)一定在pivot右側(cè)的元素中，因此拿pivot右側(cè)部分作為新數(shù)組重新進行一輪找出第k大元素的快速選擇即可。若pivot右側(cè)元素個數(shù)<k，可知，第k大的數(shù)一定在pivot左側(cè)，因此以pivot左側(cè)所有元素作為新數(shù)組，重新進行一輪快速選擇，但是k的值就變?yōu)閗-右側(cè)元素個數(shù)，因為最大的若干個元素都在pivot右側(cè)中，所以要從k中減去這些右側(cè)元素的個數(shù)。

以下是一個快速選擇的示例：

以下是基于JAVA實現(xiàn)的快速選擇的代碼，僅供參考：

public int findTopK(int[] nums, int k, int start, int end) {
        if (k <= 0) {
            throw new IllegalArgumentException("K can not less than 1!");
        } else if (k > (end - start + 1)) {
            throw new IllegalArgumentException("K out of range! start = " + start + ", end = " + end + ", k = " + k);
        }

        if (k == 1) {
            int max = Integer.MIN_VALUE;
            for (int i = start; i <= end; i++) {
                max = Math.max(max, nums[i]);
            }
            return max;
        }

        int rand = new Random().nextInt(k);
        int tmp = nums[end];
        nums[end] = nums[start + rand];
        nums[start + rand] = tmp;
        int pivot = nums[end];

        int l = start, r = start;
        while (r < end) {
            if (nums[r] > pivot) {
                r++;
            } else {
                tmp = nums[r];
                nums[r] = nums[l];
                nums[l] = tmp;
                l++;
                r++;
            }
        }

        tmp = pivot;
        nums[end] = nums[l];
        nums[l] = tmp;

        if (start + (end - start + 1) - l >= k) {// 若右側(cè)（含l）數(shù)量≥k
            return findTopK(nums, k, l, end);
        } else {// 右側(cè)（含l）數(shù)量不足k
            return findTopK(nums, k - (end - l + 1), start, l - 1);
        }
    }

快速選擇的時間復(fù)雜度是O(n)，推論依據(jù)是快速選擇每次遍歷的元素個數(shù)預(yù)期都會減半，因此全部要遍歷的元素個數(shù)是：