文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题数组中的第 K 个最大元素出处215. 数组中的第 K 个最大元素难度6 级题目描述要求给定整数数组nums \texttt{nums}nums和整数k \texttt{k}k返回数组中第k \texttt{k}k个最大的元素。注意需要返回的是数组排序后的第k \texttt{k}k个最大的元素不是第k \texttt{k}k个不同的元素。要求时间复杂度是O(n) \texttt{O(n)}O(n)。示例示例 1输入nums [3,2,1,5,6,4], k 2 \texttt{nums [3,2,1,5,6,4], k 2}nums [3,2,1,5,6,4], k 2输出5 \texttt{5}5示例 2输入nums [3,2,3,1,2,4,5,5,6], k 4 \texttt{nums [3,2,3,1,2,4,5,5,6], k 4}nums [3,2,3,1,2,4,5,5,6], k 4输出4 \texttt{4}4数据范围1 ≤ k ≤ nums.length ≤ 10 5 \texttt{1} \le \texttt{k} \le \texttt{nums.length} \le \texttt{10}^\texttt{5}1≤k≤nums.length≤105-10 4 ≤ nums[i] ≤ 10 4 \texttt{-10}^\texttt{4} \le \texttt{nums[i]} \le \texttt{10}^\texttt{4}-104≤nums[i]≤104解法思路和算法在长度为n nn的数组中寻找第k kk个最大的元素最简单的做法是将数组排序然后返回第k kk个最大的元素该做法的时间复杂度是O ( n log ⁡ n ) O(n \log n)O(nlogn)。为了将时间复杂度降低到O ( n ) O(n)O(n)需要使用快速选择算法。快速选择算法和快速排序算法相似是分治的应用。由于题目要求寻找第k kk个最大的元素因此考虑将数组降序排序排序后的数组的下标k − 1 k - 1k−1处元素即为第k kk个最大的元素。快速选择算法的操作包括选择基准元素和分区做法如下。选择基准元素。可以选择数组的首个元素作为基准元素也可以在数组中随机选择一个元素作为基准元素并将基准元素与数组的首个元素交换位置此时数组的首个元素为基准元素。分区。分区的含义是将数组分成两个子数组基准元素左侧子数组的元素都大于等于基准元素基准元素右侧子数组的元素都小于基准元素。具体做法如下。用start \textit{start}start和end \textit{end}end分别表示当前数组的开始下标和结束下标初始化两个指针low start 1 \textit{low} \textit{start} 1lowstart1和high end \textit{high} \textit{end}highend。将low \textit{low}low从左往右遍历直到遇到小于基准元素的元素将high \textit{high}high从右往左遍历直到遇到大于等于基准元素的元素。此时如果low high \textit{low} \textit{high}lowhigh则交换low \textit{low}low和high \textit{high}high处的元素。重复该操作直到low ≥ high \textit{low} \ge \textit{high}low≥high时结束该操作。将high \textit{high}high从右往左遍历直到遇到大于等于基准元素的元素。此时high \textit{high}high指向基准元素应该放置下标的位置。如果high start \textit{high} \textit{start}highstart则交换start \textit{start}start和high \textit{high}high处的元素。用pivotIndex \textit{pivotIndex}pivotIndex表示分区之后基准元素所在下标。根据pivotIndex \textit{pivotIndex}pivotIndex与k − 1 k - 1k−1的大小关系执行如下操作。如果pivotIndex k − 1 \textit{pivotIndex} k - 1pivotIndexk−1则此时的基准元素即为第k kk个最大的元素返回下标pivotIndex \textit{pivotIndex}pivotIndex处的元素。如果pivotIndex k − 1 \textit{pivotIndex} k - 1pivotIndexk−1则下标pivotIndex \textit{pivotIndex}pivotIndex处的元素小于等于第k kk个最大的元素在下标范围[ start , pivotIndex − 1 ] [\textit{start}, \textit{pivotIndex} - 1][start,pivotIndex−1]中继续寻找第k kk个最大的元素。如果数组中存在多个基准元素则可以跳过连续基准元素从而降低时间复杂度。如果pivotIndex k − 1 \textit{pivotIndex} k - 1pivotIndexk−1则下标pivotIndex \textit{pivotIndex}pivotIndex处的元素大于等于第k kk个最大的元素在下标范围[ pivotIndex 1 , end ] [\textit{pivotIndex} 1, \textit{end}][pivotIndex1,end]中继续寻找第k kk个最大的元素。快速排序算法的平均时间复杂度是O ( n log ⁡ n ) O(n \log n)O(nlogn)快速选择算法在每次分区之后都可以排除不可能包含第k kk个最大元素的子数组因此平均时间复杂度低于快速排序算法。平均情况下快速选择算法在每次分区之后都可以排除数组中的一半元素递归调用层数是O ( log ⁡ n ) O(\log n)O(logn)时间复杂度是O ( n ) O(n)O(n)空间复杂度是O ( log ⁡ n ) O(\log n)O(logn)。最差情况下快速选择算法在每次分区时选择的基准元素都是数组中的最小值或最大值递归调用层数是O ( n ) O(n)O(n)时间复杂度是O ( n 2 ) O(n^2)O(n2)空间复杂度是O ( n ) O(n)O(n)。使用随机选择基准元素的做法可以最大程度避免最差情况的发生达到O ( n ) O(n)O(n)的时间复杂度。代码classSolution{publicintfindKthLargest(int[]nums,intk){returnquickSelect(nums,k-1,0,nums.length-1);}publicintquickSelect(int[]nums,intindex,intstart,intend){intpivotIndexpartition(nums,start,end);if(pivotIndexindex){returnnums[pivotIndex];}elseif(pivotIndexindex){while(pivotIndex-1indexnums[pivotIndex-1]nums[pivotIndex]){pivotIndex--;}returnquickSelect(nums,index,start,pivotIndex-1);}else{returnquickSelect(nums,index,pivotIndex1,end);}}publicintpartition(int[]nums,intstart,intend){intrandomIndexstart(int)(Math.random()*(end-start1));swap(nums,start,randomIndex);intpivotnums[start];intlowstart,highend;while(lowhigh){while(lowhighnums[low]pivot){low;}while(lowhighnums[high]pivot){high--;}if(lowhigh){swap(nums,low,high);}}while(highstartnums[high]pivot){high--;}if(highstart){swap(nums,start,high);}returnhigh;}publicvoidswap(int[]nums,intindex1,intindex2){inttempnums[index1];nums[index1]nums[index2];nums[index2]temp;}}复杂度分析时间复杂度平均情况是O ( n ) O(n)O(n)最差情况是O ( n 2 ) O(n^2)O(n2)其中n nn是数组nums \textit{nums}nums的长度。快速选择算法的平均时间复杂度是O ( n ) O(n)O(n)最差时间复杂度是O ( n 2 ) O(n^2)O(n2)。空间复杂度平均情况是O ( log ⁡ n ) O(\log n)O(logn)最差情况是O ( n ) O(n)O(n)其中n nn是数组nums \textit{nums}nums的长度。空间复杂度取决于递归调用层数。平均情况下递归调用层数是O ( log ⁡ n ) O(\log n)O(logn)快速选择算法的空间复杂度是O ( log ⁡ n ) O(\log n)O(logn)。最差情况下递归调用层数是O ( n ) O(n)O(n)快速选择算法的空间复杂度是O ( n ) O(n)O(n)。