给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
思路：基于快排改进的快速选择算法
- 分解： 将数组 a[l⋯r] 「划分」成两个子数组 a[l⋯q−1]、a[q+1⋯r]，使得 a[l⋯q−1] 中的每个元素小于等于 a[q]，且 a[q] 小于等于 a[q+1⋯r] 中的每个元素。其中，计算下标 q 也是「划分」过程的一部分。
- 解决： 通过递归调用快速排序，对子数组 a[l⋯q−1] 和 a[q+1⋯r] 进行排序。
- 合并： 因为子数组都是原址排序的，所以不需要进行合并操作，a[l⋯r] 已经有序。
- 上文中提到的 「划分」 过程是：从子数组 a[l⋯r] 中选择任意一个元素 x 作为主元，调整子数组的元素使得左边的元素都小于等于它，右边的元素都大于等于它， x 的最终位置就是 q。
由此可以发现每次经过「划分」操作后，我们一定可以确定一个元素的最终位置，即 x 的最终位置为 q，并且保证 a[l⋯q−1] 中的每个元素小于等于 a[q]，且 a[q] 小于等于 a[q+1⋯r] 中的每个元素。所以只要某次划分的 q 为倒数第 k 个下标的时候，我们就已经找到了答案。我们只关心这一点，至于 a[l⋯q−1] 和 a[q+1⋯r] 是否是有序的，我们不关心。
在分解的过程当中，我们会对子数组进行划分，如果划分得到的 q 正好就是我们需要的下标，就直接返回 a[q]；否则，如果 q 比目标下标小，就递归右子区间，否则递归左子区间。这样就可以把原来递归两个区间变成只递归一个区间，提高了时间效率。这就是「快速选择」算法。
平均情况下，快速选择算法在每次分区之后都可以排除数组中的一半元素，递归调用层数是 O(logn)，时间复杂度是 O(n)，空间复杂度是 O(logn)。最差情况下，快速选择算法在每次分区时选择的基准元素都是数组中的最小值或最大值，递归调用层数是 O(n)，时间复杂度是 O()，空间复杂度是 O(n)。
使用随机选择基准元素的做法可以最大程度避免最差情况的发生，达到 O(n) 的时间复杂度。
public class Solution {Random random = new Random();public int FindKthLargest(int[] nums, int k) {int right = nums.Length;return Select(nums, k - 1, 0, right - 1);}public int Select(int[] nums, int index, int left, int right){int pivotIndex = QuickSort(nums, left, right);if(pivotIndex == index)return nums[pivotIndex];else if(pivotIndex > index)return Select(nums, index, left, pivotIndex - 1);elsereturn Select(nums, index, pivotIndex + 1, right);}public int QuickSort(int[] nums, int left, int right){int randomIndex = left + random.Next(right - left + 1);int tempLeft = left + 1, tempRight = right;Swap(nums, randomIndex, left);int pivot = nums[left];while(tempLeft < tempRight){while(tempLeft < tempRight &&nums[tempRight] < pivot){tempRight--;//从右往左遍历，直到遇到大于等于基准元素的元素}while(tempLeft < tempRight &&nums[tempLeft] >= pivot){tempLeft++;//从左往右遍历，直到遇到小于基准元素的元素}if(tempLeft < tempRight)Swap(nums, tempLeft, tempRight);}while(tempRight > left && nums[tempRight] < pivot)//找基准元素应该在的位置tempRight--;if(tempRight > left)Swap(nums, left, tempRight);return tempRight;}public void Swap(int[] nums, int index1, int index2){int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;}
}复杂度分析
- 时间复杂度：平均情况是 O(n)，最差情况是 O(n^2)，其中 n 是数组 nums 的长度。快速选择算法的平均时间复杂度是 O(n)，最差时间复杂度是 O(n^2)。
-
空间复杂度：平均情况是 O(logn)，最差情况是 O(n)，其中 n 是数组 nums 的长度。空间复杂度取决于递归调用层数。平均情况下，递归调用层数是 O(logn)，快速选择算法的空间复杂度是 O(logn)。最差情况下，递归调用层数是 O(n)，快速选择算法的空间复杂度是 O(n)。
