企业官网建设流程全解析

LeetCode-Go 题解 215：数组中第 K 个最大元素与快速选择算法全解析

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本篇文章围绕 LeetCode 第 215 题「Kth Largest Element in an Array（数组中的第 K 个最大元素）」展开，以开源仓库 LeetCode-Go 中leetcode/0215.Kth-Largest-Element-in-an-Array/目录下的 README、核心实现与测试代码为依托，完整剖析快速选择（Quickselect）算法的 partition 原理、Go 源码实现细节、复杂度边界，并延伸讲解仓库中附带的排序解法与剑指 Offer 40「最小的 k 个数」扩展题。读完本文，你将掌握如何用平均 O(n) 时间复杂度在无序数组中定位第 K 大元素，并能直接复用仓库中已验证的高质量 Go 实现。

题目描述

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

在一个未排序的数组中找出第 K 大的元素。需要注意：这里指的是排序后的第 K 大元素，而不是第 K 个互不相同的元素。也就是说，数组中的重复元素要分别计入排名。

示例 1：

Input: [3,2,1,5,6,4] and k = 2 Output: 5

数组排序后为[1,2,3,4,5,6]，第 2 大元素为5。

示例 2：

Input: [3,2,3,1,2,4,5,5,6] and k = 4 Output: 4

数组排序后为[1,2,2,3,3,4,5,5,6]，其中4与5重复出现。按"排序后位置"计，第 4 大元素为4（注意5占两个位置，重复元素被计入）。

注意事项：

You may assume k is always valid, 1 ≤ k ≤ array's length.

题目保证k恒有效，即1 ≤ k ≤ 数组长度，因此无需处理k越界的边界情况。

题目大意

找出数组中第 K 大的元素。这一题非常经典，是各大公司面试中的高频题。朴素做法是先排序再取下标，时间复杂度为 O(n log n)；而借助快速选择（Quickselect）思想，可以在O(n) 的平均时间复杂度内完成求解，这也是本仓库实现的核心。

解题思路：利用 partition 的下标性质

原文档给出的核心思路是快速选择 Quickselect，其理论根基在于快速排序的 partition 操作：

在快速选择 quickselect 的 partition 操作中，每次 partition 操作结束都会返回一个点，这个标定点的下标和最终排序之后有序数组中这个元素所在的下标是一致的。

这句话是整道题的关键。快速排序的单趟 partition 会选定一个标定点（pivot），把小于等于它的元素放到左侧、大于它的元素放到右侧，最后标定点落到它"最终应该在"的位置上——即使整个数组还没有完全有序，该元素与最终完全排序后它所处的位置下标完全一致。

利用这个特性，我们无需把数组完整排序，只需不断地缩小搜索区间，最终找到第 K 大的元素：

• 执行一次 partition 操作后，若标定点的下标比 K 小（标定点在当前搜索区间的左侧），说明第 K 大的元素一定在后边的区间，继续对右半区间执行 partition；
• 若标定点的下标比 K 大，说明第 K 大的元素在左边的区间，继续对左半区间执行 partition；
• 若下标与 K 相等，直接输出该下标对应的数组元素即可。

每一次 partition 都会淘汰掉一半左右的元素，因此整体期望时间复杂度为 O(n)。

仓库源码精读：三个关键函数

仓库中 215. Kth Largest Element in an Array.go 用三个函数完整落地了上述思路。先看对外入口：

// 解法二 这个方法的理论依据是 partition 得到的点的下标就是最终排序之后的下标，根据这个下标，我们可以判断第 K 大的数在哪里 // 时间复杂度 O(n)，空间复杂度 O(log n)，最坏时间复杂度为 O(n^2)，空间复杂度 O(n) func findKthLargest(nums []int, k int) int { m := len(nums) - k + 1 // mth smallest, from 1..len(nums) return selectSmallest(nums, 0, len(nums)-1, m) }

这里有一个非常巧妙的转换：第 K 大 = 第 (len(nums) - K + 1) 小。例如len = 6, k = 2时，第 2 大即第6 - 2 + 1 = 5小。把"找第 K 大"统一转换为"找第 m 小"，代码就可以复用同一套递归逻辑。

接下来是递归主体selectSmallest：

func selectSmallest(nums []int, l, r, i int) int { if l >= r { return nums[l] } q := partition(nums, l, r) k := q - l + 1 if k == i { return nums[q] } if i < k { return selectSmallest(nums, l, q-1, i) } else { return selectSmallest(nums, q+1, r, i-k) } }

递归逻辑与原文档描述完全对应：

• partition返回标定点最终下标q，k = q - l + 1表示标定点在当前子区间内是第k小；
• 若k == i，说明标定点正是要找的第i小元素，直接返回nums[q]；
• 若i < k，目标在左侧区间[l, q-1]，继续递归，且i不变；
• 否则目标在右侧区间[q+1, r]，继续递归，但此时的排名要减去已淘汰的左侧元素数，即i-k。

注意递归基l >= r：当区间收缩到只剩一个元素时，该元素必然就是目标，直接返回。

最后是 partition 实现：

func partition(nums []int, l, r int) int { k := l + rand.Intn(r-l+1) // 此处为优化，使得时间复杂度期望降为 O(n)，最坏时间复杂度为 O(n^2) nums[k], nums[r] = nums[r], nums[k] i := l - 1 // nums[l..i] <= nums[r] // nums[i+1..j-1] > nums[r] for j := l; j < r; j++ { if nums[j] <= nums[r] { i++ nums[i], nums[j] = nums[j], nums[i] } } nums[i+1], nums[r] = nums[r], nums[i+1] return i + 1 }

该 partition 是经典的随机化 Lomuto 划分，值得逐行拆解：

1. k := l + rand.Intn(r-l+1)先从当前区间中随机选取一个元素作为标定点，并把它交换到区间末尾nums[r]。随机化是保证期望 O(n) 的关键：如果固定取第一个或最后一个元素，面对已经有序的输入时每次划分都会退化，最坏时间复杂度变为 O(n²)；
2. 指针i维护"小于等于区间的右边界"，循环用j扫描[l, r-1]；
3. 凡是nums[j] <= nums[r]的元素都交换进左侧"小于等于区"，循环结束后nums[l..i]全部 ≤ 标定点，nums[i+1..j-1]全部 > 标定点；
4. 最后把标定点从nums[r]交换回nums[i+1]，此时标定点落位，其下标i+1就是它在完全有序数组中的最终下标，返回之。

import ( "math/rand" "sort" )

源码引入math/rand用于随机化选点，引入sort服务于下面的排序解法。

解法对比：排序法 vs 快速选择法

同一文件中还保留着另一种解法，注释直言其速度反而是最快的：

// 解法一 排序，排序的方法反而速度是最快的 func findKthLargest1(nums []int, k int) int { sort.Ints(nums) return nums[len(nums)-k] }

两种解法对比如下：

从仓库实测看，sort.Ints由 Go 标准库基于 pdqsort 实现，常数极小，因此在常规输入规模下排序法反而更快。这提醒我们：算法题解中的理论复杂度与实际运行速度不一定正相关，理解两种方案的取舍比背诵结论更重要。

测试验证：六组用例全量覆盖

仓库为本题提供了完整的表驱动测试，见 215. Kth Largest Element in an Array_test.go。测试用例覆盖了多种边界与典型场景：

测试逻辑本身有两个值得借鉴的工程细节：

• clone215辅助函数在每次调用前复制切片，因为findKthLargest、findKthLargest1都是就地改写传入切片（partition 会交换元素），多个解法共享同一份输入时，必须各自持有独立副本，避免相互污染；
• 同一个用例同时用findKthLargest（快速选择）与findKthLargest1（排序）两个实现断言，got != a.one || got1 != a.one时立即t.Fatalf报错，实现"双实现交叉验证"。

扩展：由"第 K 大"到"最小的 k 个数"（剑指 Offer 40）

仓库源码在本题基础上还附带了一个经典扩展题——剑指 Offer 40「最小的 k 个数」：

// 扩展题 剑指 Offer 40. 最小的 k 个数 func getLeastNumbers(arr []int, k int) []int { return selectSmallest1(arr, 0, len(arr)-1, k)[:k] }

其实现selectSmallest1与selectSmallest完全一致，区别仅在于：找到第 k 小元素后不再返回单个值，而是直接返回整个数组。由于 partition 完成后，第 k 小元素左侧的所有元素都 ≤ 它，此时nums[:k]恰好就是"最小的 k 个数"（顺序不定，但元素集合正确）：

// 和 selectSmallest 实现完全一致，只是返回值不用再截取了，直接返回 nums 即可 func selectSmallest1(nums []int, l, r, i int) []int { if l >= r { return nums } q := partition(nums, l, r) k := q - l + 1 if k == i { return nums } if i < k { return selectSmallest1(nums, l, q-1, i) } else { return selectSmallest1(nums, q+1, r, i-k) } }

这一步映射非常自然：找第 K 大的元素与找最小的 K 个数本质上共享同一套"划分-收缩"框架，partition返回的标定点下标即"第 (下标+1) 小元素"的位置。掌握第 215 题的快速选择实现后，剑指 Offer 40 只需改动返回值即可直接复用，这也是仓库将两者放在同一文件中的原因。对应测试中通过len(least) != p.two校验返回个数，验证了扩展函数的正确性。

复杂度与适用前提小结

综合源码注释与实现可以确认：

• 快速选择解法平均时间复杂度 O(n)，平均空间复杂度 O(log n)（递归栈深度）；最坏情况为 O(n²) 时间、O(n) 空间，此时输入会退化为每次划分严重失衡（但随机化选点已极大降低该概率）；
• 排序解法时间复杂度 O(n log n)，空间复杂度 O(1)，常数小、行为稳定；
• 两个解法均就地修改输入切片，若调用方需要保留原数组，必须先复制，正如测试中的clone215所做；
• 题目保证1 ≤ k ≤ len(nums)，实现无需处理k越界。

在实际面试与竞赛场景中，若对输入分布一无所知，推荐优先采用随机化快速选择方案；若数据规模较小或对最坏情况敏感，直接排序取下标往往更稳妥。你可以通过go test ./leetcode/0215.Kth-Largest-Element-in-an-Array/ -run Test_Problem215 -v在本仓库中复现上述全部用例，进一步验证两种解法的正确性。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go