文章目录
- 题目
- 标题和出处
- 难度
- 题目描述
- 要求
- 示例
- 数据范围
- 解法
- 思路和算法
- 代码
- 复杂度分析
题目
标题和出处
标题：数组中的第 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} + 1low=start+1和high = end \textit{high} = \textit{end}high=end。
将low \textit{low}low从左往右遍历，直到遇到小于基准元素的元素；将high \textit{high}high从右往左遍历，直到遇到大于等于基准元素的元素。此时如果low < high \textit{low} < \textit{high}low<high，则交换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}high>start，则交换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 - 1pivotIndex=k−1，则此时的基准元素即为第k kk个最大的元素，返回下标pivotIndex \textit{pivotIndex}pivotIndex处的元素。
如果pivotIndex > k − 1 \textit{pivotIndex} > k - 1pivotIndex>k−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 - 1pivotIndex<k−1，则下标pivotIndex \textit{pivotIndex}pivotIndex处的元素大于等于第k kk个最大的元素，在下标范围[ pivotIndex + 1 , end ] [\textit{pivotIndex} + 1, \textit{end}][pivotIndex+1,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){intpivotIndex=partition(nums,start,end);if(pivotIndex==index){returnnums[pivotIndex];}elseif(pivotIndex>index){while(pivotIndex-1>index&&nums[pivotIndex-1]==nums[pivotIndex]){pivotIndex--;}returnquickSelect(nums,index,start,pivotIndex-1);}else{returnquickSelect(nums,index,pivotIndex+1,end);}}publicintpartition(int[]nums,intstart,intend){intrandomIndex=start+(int)(Math.random()*(end-start+1));swap(nums,start,randomIndex);intpivot=nums[start];intlow=start,high=end;while(low<high){while(low<high&&nums[low]>=pivot){low++;}while(low<high&&nums[high]<pivot){high--;}if(low<high){swap(nums,low,high);}}while(high>start&&nums[high]<pivot){high--;}if(high>start){swap(nums,start,high);}returnhigh;}publicvoidswap(int[]nums,intindex1,intindex2){inttemp=nums[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)。
