尧图网站建设 
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 个互不相同的元素。也就是说数组中的重复元素要分别计入排名。示例 1Input: [3,2,1,5,6,4] and k 2 Output: 5数组排序后为[1,2,3,4,5,6]第 2 大元素为5。示例 2Input: [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 ≤ arrays 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 小代码就可以复用同一套递归逻辑。接下来是递归主体selectSmallestfunc 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, q1, r, i-k) } }递归逻辑与原文档描述完全对应partition返回标定点最终下标qk q - l 1表示标定点在当前子区间内是第k小若k i说明标定点正是要找的第i小元素直接返回nums[q]若i k目标在左侧区间[l, q-1]继续递归且i不变否则目标在右侧区间[q1, r]继续递归但此时的排名要减去已淘汰的左侧元素数即i-k。注意递归基l r当区间收缩到只剩一个元素时该元素必然就是目标直接返回。最后是 partition 实现func partition(nums []int, l, r int) int { k : l rand.Intn(r-l1) // 此处为优化使得时间复杂度期望降为 O(n)最坏时间复杂度为 O(n^2) nums[k], nums[r] nums[r], nums[k] i : l - 1 // nums[l..i] nums[r] // nums[i1..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[i1], nums[r] nums[r], nums[i1] return i 1 }该 partition 是经典的随机化 Lomuto 划分值得逐行拆解k : l rand.Intn(r-l1)先从当前区间中随机选取一个元素作为标定点并把它交换到区间末尾nums[r]。随机化是保证期望 O(n) 的关键如果固定取第一个或最后一个元素面对已经有序的输入时每次划分都会退化最坏时间复杂度变为 O(n²)指针i维护小于等于区间的右边界循环用j扫描[l, r-1]凡是nums[j] nums[r]的元素都交换进左侧小于等于区循环结束后nums[l..i]全部 ≤ 标定点nums[i1..j-1]全部 标定点最后把标定点从nums[r]交换回nums[i1]此时标定点落位其下标i1就是它在完全有序数组中的最终下标返回之。import ( math/rand sort )源码引入math/rand用于随机化选点引入sort服务于下面的排序解法。解法对比排序法 vs 快速选择法同一文件中还保留着另一种解法注释直言其速度反而是最快的// 解法一 排序排序的方法反而速度是最快的 func findKthLargest1(nums []int, k int) int { sort.Ints(nums) return nums[len(nums)-k] }两种解法对比如下维度解法一排序法解法二快速选择法核心思路全量排序后按下标取随机化 partition 逐步收缩区间时间复杂度O(n log n)稳定平均 O(n)最坏 O(n²)空间复杂度O(1)sort.Ints就地排序平均 O(log n) 递归栈最坏 O(n)适用场景对最坏情况敏感、要求绝对稳定追求平均线性时间、数据规模大从仓库实测看sort.Ints由 Go 标准库基于 pdqsort 实现常数极小因此在常规输入规模下排序法反而更快。这提醒我们算法题解中的理论复杂度与实际运行速度不一定正相关理解两种方案的取舍比背诵结论更重要。测试验证六组用例全量覆盖仓库为本题提供了完整的表驱动测试见 215. Kth Largest Element in an Array_test.go。测试用例覆盖了多种边界与典型场景输入数组k期望输出覆盖点[3,2,1]22常规小数组[3,2,1,5,6,4]25题目示例 1[3,2,3,1,2,4,5,5,6]44题目示例 2含重复元素[0,0,0,0,0]20全相同元素[1]11单元素边界[3,2,3,1,2,4,5,5,6,7,7,8,2,3,1,1,1,10,11,5,6,2,4,7,8,5,6]202长数组 大量重复测试逻辑本身有两个值得借鉴的工程细节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, q1, 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解 215：数组中第 K 个最大元素与快速选择算法全解析
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 个互不相同的元素。也就是说数组中的重复元素要分别计入排名。示例 1Input: [3,2,1,5,6,4] and k 2 Output: 5数组排序后为[1,2,3,4,5,6]第 2 大元素为5。示例 2Input: [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 ≤ arrays 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 小代码就可以复用同一套递归逻辑。接下来是递归主体selectSmallestfunc 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, q1, r, i-k) } }递归逻辑与原文档描述完全对应partition返回标定点最终下标qk q - l 1表示标定点在当前子区间内是第k小若k i说明标定点正是要找的第i小元素直接返回nums[q]若i k目标在左侧区间[l, q-1]继续递归且i不变否则目标在右侧区间[q1, r]继续递归但此时的排名要减去已淘汰的左侧元素数即i-k。注意递归基l r当区间收缩到只剩一个元素时该元素必然就是目标直接返回。最后是 partition 实现func partition(nums []int, l, r int) int { k : l rand.Intn(r-l1) // 此处为优化使得时间复杂度期望降为 O(n)最坏时间复杂度为 O(n^2) nums[k], nums[r] nums[r], nums[k] i : l - 1 // nums[l..i] nums[r] // nums[i1..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[i1], nums[r] nums[r], nums[i1] return i 1 }该 partition 是经典的随机化 Lomuto 划分值得逐行拆解k : l rand.Intn(r-l1)先从当前区间中随机选取一个元素作为标定点并把它交换到区间末尾nums[r]。随机化是保证期望 O(n) 的关键如果固定取第一个或最后一个元素面对已经有序的输入时每次划分都会退化最坏时间复杂度变为 O(n²)指针i维护小于等于区间的右边界循环用j扫描[l, r-1]凡是nums[j] nums[r]的元素都交换进左侧小于等于区循环结束后nums[l..i]全部 ≤ 标定点nums[i1..j-1]全部 标定点最后把标定点从nums[r]交换回nums[i1]此时标定点落位其下标i1就是它在完全有序数组中的最终下标返回之。import ( math/rand sort )源码引入math/rand用于随机化选点引入sort服务于下面的排序解法。解法对比排序法 vs 快速选择法同一文件中还保留着另一种解法注释直言其速度反而是最快的// 解法一 排序排序的方法反而速度是最快的 func findKthLargest1(nums []int, k int) int { sort.Ints(nums) return nums[len(nums)-k] }两种解法对比如下维度解法一排序法解法二快速选择法核心思路全量排序后按下标取随机化 partition 逐步收缩区间时间复杂度O(n log n)稳定平均 O(n)最坏 O(n²)空间复杂度O(1)sort.Ints就地排序平均 O(log n) 递归栈最坏 O(n)适用场景对最坏情况敏感、要求绝对稳定追求平均线性时间、数据规模大从仓库实测看sort.Ints由 Go 标准库基于 pdqsort 实现常数极小因此在常规输入规模下排序法反而更快。这提醒我们算法题解中的理论复杂度与实际运行速度不一定正相关理解两种方案的取舍比背诵结论更重要。测试验证六组用例全量覆盖仓库为本题提供了完整的表驱动测试见 215. Kth Largest Element in an Array_test.go。测试用例覆盖了多种边界与典型场景输入数组k期望输出覆盖点[3,2,1]22常规小数组[3,2,1,5,6,4]25题目示例 1[3,2,3,1,2,4,5,5,6]44题目示例 2含重复元素[0,0,0,0,0]20全相同元素[1]11单元素边界[3,2,3,1,2,4,5,5,6,7,7,8,2,3,1,1,1,10,11,5,6,2,4,7,8,5,6]202长数组 大量重复测试逻辑本身有两个值得借鉴的工程细节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, q1, 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考