在面試字節(jié)跳動(dòng)的過(guò)程中，現(xiàn)場(chǎng)寫(xiě)算法代碼是繞不開(kāi)的一個(gè)環(huán)節(jié)。其中快速排序(Quick Sort)、快速選擇(Quick Select)是最常見(jiàn)的算法題之一?？焖龠x擇是目前解決TopK問(wèn)題的最優(yōu)算法，如果想拿下字節(jié)跳動(dòng)的offer，快速排序算法是必須要掌握的算法之一！
開(kāi)篇先出到面試題，請(qǐng)讀者思考一下可能的解法：
給你一個(gè)無(wú)序數(shù)組，請(qǐng)找出其中第K大的數(shù)，時(shí)間復(fù)雜度控制在O(N)。
如果不對(duì)時(shí)間復(fù)雜度加約束的情況下，該題有很多種可能解法，例如：
- 用任意一種性能不錯(cuò)的排序算法先將數(shù)組進(jìn)行排序，然后從中找到位置k的數(shù)值。但即便用當(dāng)前最好的排序算法，時(shí)間復(fù)雜度也是在O(n·log n)的級(jí)別，不符合題目要求。
- 用大頂堆算法，僅保留K個(gè)最大的值。這種算法的時(shí)間復(fù)雜度雖然優(yōu)于前面一種，但時(shí)間復(fù)雜度也是O(n·log k)的級(jí)別，依然不滿足題目要求。
因此，為了達(dá)到題目中要求，就必須要引出今天的主角：快速選擇算法(Quick Select)?？焖龠x擇算法是目前解決TopK問(wèn)題的最優(yōu)解。其核心思想和快速排序類似，因?yàn)檫@兩個(gè)經(jīng)典算法的提出者都是同一個(gè)人——C.A.R.Hoare。
快速選擇的執(zhí)行步驟是先從數(shù)組中隨機(jī)選擇一個(gè)元素作為pivot，然后遍歷數(shù)組，將<pivot的元素都放在pivot左側(cè)，≥pivot的元素都放在pivot右側(cè)。如此遍歷完以后，如果要找第k大的數(shù)，可以判斷pivot兩側(cè)元素個(gè)數(shù)。假設(shè)pivot右側(cè)元素個(gè)數(shù)≥k可推斷出，第k大的數(shù)一定在pivot右側(cè)的元素中，因此拿pivot右側(cè)部分作為新數(shù)組重新進(jìn)行一輪找出第k大元素的快速選擇即可。若pivot右側(cè)元素個(gè)數(shù)<k，可知，第k大的數(shù)一定在pivot左側(cè)，因此以pivot左側(cè)所有元素作為新數(shù)組，重新進(jìn)行一輪快速選擇，但是k的值就變?yōu)閗-右側(cè)元素個(gè)數(shù)，因?yàn)樽畲蟮娜舾蓚€(gè)元素都在pivot右側(cè)中，所以要從k中減去這些右側(cè)元素的個(gè)數(shù)。
以下是一個(gè)快速選擇的示例：
以下是基于JAVA實(shí)現(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);
}
}
快速選擇的時(shí)間復(fù)雜度是O(n)，推論依據(jù)是快速選擇每次遍歷的元素個(gè)數(shù)預(yù)期都會(huì)減半，因此全部要遍歷的元素個(gè)數(shù)是：
Sn = n + n/2 + n/4 + …… + 1
這是一個(gè)典型的等比數(shù)列求和，套用等比數(shù)列求和公式可得：
Sn = n + n/2 + n/4 + …… + 1 = (a1 - an · q) / (1 - q)= (n - 0.5) / 0.5 = 2n - 1
去除不必要的常數(shù)，僅保留數(shù)量級(jí)之后可得，快速排序的預(yù)期時(shí)間復(fù)雜度是O(n)
現(xiàn)如今互聯(lián)網(wǎng)求職競(jìng)爭(zhēng)越發(fā)激烈，難度越發(fā)困難，如果不做好充足的復(fù)習(xí)，很可能會(huì)喪失寶貴的面試機(jī)會(huì)！關(guān)注我，定期高頻更新優(yōu)質(zhì)面試寶典，幫助你在職場(chǎng)中平步青云，斬獲理想offer！
