LeetCode 215数组中的第K个最大元素 | 快速选择与堆排序引言数组中的第K个最大元素Kth Largest Element in an Array是 LeetCode 第 215 题难度为 Medium。题目要求在未排序的数组中找到第 K 个最大的元素注意这里说的是第 K 个最大不是第 K 个不同。这道题有多种解法可以使用排序找到第 K 个最大元素可以使用堆排序可以使用快速选择算法。不同的方法有不同的时间复杂度排序是 O(n log n)堆排序是 O(n log k)快速选择是 O(n) 平均时间复杂度。本文将详细分析各种解法及其优劣。问题分析题目描述给定整数数组 nums 和整数 k返回第 k 个最大的元素。例如输入 [3,2,1,5,6,4] 和 k 2返回 5因为排序后数组为 [1,2,3,4,5,6]第 2 个最大的元素是 5。问题特点注意区分第 K 个最大和第 K 个不同最大的概念。在 [2, 2] 中第 1 个最大是 2第 2 个最大也是 2即使只有一个不同的值。题目要求的是第 K 个最大允许重复。另一种理解是将数组降序排序后的第 K-1 个索引位置的元素。解法一排序最直接的解法def findKthLargest_sort(nums, k): nums.sort(reverseTrue) return nums[k - 1]排序后直接返回第 K 个元素。简单直接但时间复杂度为 O(n log n)。复杂度分析时间复杂度O(n log n)空间复杂度O(1)如果原地排序或 O(n)如果使用额外空间解法二堆排序使用最大堆import heapq def findKthLargest_heap(nums, k): return heapq.nlargest(k, nums)[-1]heapq.nlargest(k, nums) 返回最大的 k 个元素时间复杂度为 O(n log k)。原地堆排序def findKthLargest_heap_sort(nums, k): n len(nums) def heapify(nums, n, i): largest i left 2 * i 1 right 2 * i 2 if left n and nums[left] nums[largest]: largest left if right n and nums[right] nums[largest]: largest right if largest ! i: nums[i], nums[largest] nums[largest], nums[i] heapify(nums, n, largest) for i in range(n // 2 - 1, -1, -1): heapify(nums, n, i) for i in range(n - 1, n - k, -1): nums[0], nums[i] nums[i], nums[0] heapify(nums, i, 0) return nums[0]复杂度分析时间复杂度O(n log k)空间复杂度O(1)原地解法三快速选择算法原理快速选择算法是快速排序的变体。与快速排序递归处理两部分不同快速选择只处理包含目标元素的那一部分从而将平均时间复杂度降低到 O(n)。import random def findKthLargest_quick_select(nums, k): target len(nums) - k def quick_select(left, right): pivot random.choice(range(left, right 1)) nums[pivot], nums[right] nums[right], nums[pivot] pivot_val nums[right] i left for j in range(left, right): if nums[j] pivot_val: nums[i], nums[j] nums[j], nums[i] i 1 nums[i], nums[right] nums[right], nums[i] if i target: return nums[i] elif i target: return quick_select(i 1, right) else: return quick_select(left, i - 1) return quick_select(0, len(nums) - 1)复杂度分析平均时间复杂度O(n)最坏时间复杂度O(n²)空间复杂度O(log n)递归栈快速选择详解分区操作快速选择的核心是分区操作。选择一个 pivot 元素将数组分为两部分小于等于 pivot 的元素在左边大于 pivot 的元素在右边。分区后pivot 元素所在的位置是它在排序后数组中的正确位置。递归策略如果 pivot 的位置正好是目标位置target直接返回 pivot。如果 pivot 在目标位置右边递归处理左边部分。如果 pivot 在目标位置左边递归处理右边部分。随机化优化为避免最坏情况每次 pivot 都是最大或最小采用随机选择 pivot 的策略。这使得最坏情况发生的概率极低。代码实现Python 实现import random def findKthLargest(nums, k): target len(nums) - k def quick_select(left, right): pivot_idx random.randint(left, right) nums[pivot_idx], nums[right] nums[right], nums[pivot_idx] pivot nums[right] i left for j in range(left, right): if nums[j] pivot: nums[i], nums[j] nums[j], nums[i] i 1 nums[i], nums[right] nums[right], nums[i] if i target: return nums[i] elif i target: return quick_select(left, i - 1) else: return quick_select(i 1, right) return quick_select(0, len(nums) - 1)Java 实现public int findKthLargest(int[] nums, int k) { int target nums.length - k; return quickSelect(nums, 0, nums.length - 1, target); } private int quickSelect(int[] nums, int left, int right, int target) { int pivotIdx left (int)(Math.random() * (right - left 1)); int pivot nums[pivotIdx]; swap(nums, pivotIdx, right); int i left; for (int j left; j right; j) { if (nums[j] pivot) { swap(nums, i, j); i; } } swap(nums, i, right); if (i target) { return nums[i]; } else if (i target) { return quickSelect(nums, i 1, right, target); } else { return quickSelect(nums, left, i - 1, target); } } private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; }复杂度分析排序方法时间复杂度O(n log n)空间复杂度O(1) 或 O(n)堆方法时间复杂度O(n log k)空间复杂度O(1)快速选择方法平均时间复杂度O(n)最坏时间复杂度O(n²)空间复杂度O(log n)边界情况处理空数组当数组为空时不存在第 K 个最大元素应返回特定值或抛出异常。K 超出范围当 k 0 或 k 数组长度时应返回特定值或抛出异常。重复元素当数组包含大量重复元素时各种方法都能正确处理。全相同元素当所有元素都相同时第 K 个最大就是该元素各种方法都能正确处理。测试用例def test_find_kth_largest(): assert findKthLargest([3, 2, 1, 5, 6, 4], 2) 5 assert findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4) 4 assert findKthLargest([1], 1) 1 assert findKthLargest([1, 2], 2) 1 assert findKthLargest([2, 2, 2, 2], 3) 2 assert findKthLargest([5, 5, 5, 5], 1) 5 print(所有测试用例通过)实际应用场景第 K 个最大元素问题在现实中有很多应用。在数据分析中可以用来找中位数前 n/2 个最大或百分位数。在排行榜系统中可以用来找 Top K。在大数据处理中可以用来找最大的 K 个值而不需要完全排序。快速选择算法在计算机科学中有广泛应用如快速查找第 K 小的元素、寻找第 K 小的距离对等。总结第 K 个最大元素问题展示了多种排序和选择算法的应用排序方法简单直接适用于一般场景堆方法适合 Top K 问题时间复杂度 O(n log k)快速选择是最优方法平均 O(n) 时间但最坏情况需要注意在实际应用中应该根据数据规模和特点选择合适的算法。