字节跳动面试必会：快速选择算法，TopK问题最优解
在面试字节跳动的过程中，现场写算法代码是绕不开的一个环节。其中快速排序(Quick Sort)、快速选择(Quick Select)是最常见的算法题之一。快速选择是目前解决TopK问题的最优算法，如果想拿下字节跳动的offer，快速排序算法是必须要掌握的算法之一！
开篇先出到面试题，请读者思考一下可能的解法：
给你一个无序数组，请找出其中第K大的数，时间复杂度控制在O(N)。
如果不对时间复杂度加约束的情况下，该题有很多种可能解法，例如：
- 用任意一种性能不错的排序算法先将数组进行排序，然后从中找到位置k的数值。但即便用当前最好的排序算法，时间复杂度也是在O(n·log n)的级别，不符合题目要求。
- 用大顶堆算法，仅保留K个最大的值。这种算法的时间复杂度虽然优于前面一种，但时间复杂度也是O(n·log k)的级别，依然不满足题目要求。
因此，为了达到题目中要求，就必须要引出今天的主角：快速选择算法(Quick Select)。快速选择算法是目前解决TopK问题的最优解。其核心思想和快速排序类似，因为这两个经典算法的提出者都是同一个人——C.A.R.Hoare。
快速选择的执行步骤是先从数组中随机选择一个元素作为pivot，然后遍历数组，将<pivot的元素都放在pivot左侧，≥pivot的元素都放在pivot右侧。如此遍历完以后，如果要找第k大的数，可以判断pivot两侧元素个数。假设pivot右侧元素个数≥k可推断出，第k大的数一定在pivot右侧的元素中，因此拿pivot右侧部分作为新数组重新进行一轮找出第k大元素的快速选择即可。若pivot右侧元素个数<k，可知，第k大的数一定在pivot左侧，因此以pivot左侧所有元素作为新数组，重新进行一轮快速选择，但是k的值就变为k-右侧元素个数，因为最大的若干个元素都在pivot右侧中，所以要从k中减去这些右侧元素的个数。
以下是一个快速选择的示例：
以下是基于JAVA实现的快速选择的代码，仅供参考：
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) {// 若右侧（含l）数量≥k
return findTopK(nums, k, l, end);
} else {// 右侧（含l）数量不足k
return findTopK(nums, k - (end - l + 1), start, l - 1);
}
}
快速选择的时间复杂度是O(n)，推论依据是快速选择每次遍历的元素个数预期都会减半，因此全部要遍历的元素个数是：
Sn = n + n/2 + n/4 + …… + 1
这是一个典型的等比数列求和，套用等比数列求和公式可得：
Sn = n + n/2 + n/4 + …… + 1 = (a1 - an · q) / (1 - q)= (n - 0.5) / 0.5 = 2n - 1
去除不必要的常数，仅保留数量级之后可得，快速排序的预期时间复杂度是O(n)
现如今互联网求职竞争越发激烈，难度越发困难，如果不做好充足的复习，很可能会丧失宝贵的面试机会！关注我，定期高频更新优质面试宝典，帮助你在职场中平步青云，斩获理想offer！
