字节跳动面试必会：快速选择算法，TopK问题最优解 _快速选择算法

在面试字节跳动的过程中，现场写算法代码是绕不开的一个环节。其中快速排序(Quick Sort)、快速选择(Quick Select)是最常见的算法题之一。快速选择是目前解决TopK问题的最优算法，如果想拿下字节跳动的offer ，快速排序算法是必须要掌握的算法之一！

文章插图

开篇先出到面试题，请读者思考一下可能的解法：

【字节跳动面试必会：快速选择算法，TopK问题最优解】给你一个无序数组，请找出其中第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）数量≥kreturn findTopK(nums, k, l, end);} else {// 右侧（含l）数量不足kreturn findTopK(nums, k - (end - l + 1), start, l - 1);}}

快速选择的时间复杂度是O(n) ，推论依据是快速选择每次遍历的元素个数预期都会减半，因此全部要遍历的元素个数是：