大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定一个整数数组和整数k，返回数组中第k个最大的元素。”
2、题目描述
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1： 输入: [3,2,1,5,6,4], k = 2 输出: 5
示例 2： 输入: [3,2,3,1,2,4,5,5,6], k = 4 输出: 4
二、解题
1、思路分析
这道题要求数数组中第k个最大的元素。
主要思路就是先排序，然后找到第k个最大的元素即可。
排序有很多种排序方法，比如快速排序、插入排序。
这道题就可以使用快速排序，快速排序的步骤就是将排序的数组分成两个子数组，然后分别排序。
之后再进行合并。
在对数组进行划分的时候，可以发现，确定一个元素的最终位置，即 x 的最终位置为 q，并且保证这个区间中的每个元素小于等于 a[q]，且 a[q] 小于等于 这个区间 中的每个元素。
所以只要某次划分的 q 为倒数第 k 个下标的时候，我们就已经找到了答案。
在分解的过程中，对子数组进行划分，会出现两种情况：
- 1、划分得到的q正好是我们需要的下标，直接返回a[q]
- 2、如果q比目标下标小，就递归右子区间，否则递归左子区间
这样将原来递归两个区间变成递归一个区间，提高了时间效率。
2、代码实现
代码参考：
class Solution { Random random = new Random(); public int findKthLargest(int[] nums, int k) { return quickSelect(nums, 0, nums.length - 1, nums.length - k); } public int quickSelect(int[] a, int l, int r, int index) { int q = randomPartition(a, l, r); if (q == index) { return a[q]; } else { return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index); } } public int randomPartition(int[] a, int l, int r) { int i = random.nextInt(r - l + 1) + l; swap(a, i, r); return partition(a, l, r); } public int partition(int[] a, int l, int r) { int x = a[r], i = l - 1; for (int j = l; j < r; ++j) { if (a[j] <= x) { swap(a, ++i, j); } } swap(a, i + 1, r); return i + 1; } public void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } }
3、时间复杂度
时间复杂度：O(n)
其中n是数组的长度。
空间复杂度：O(log n)
递归使用栈空间的空间代价的期望为O(log n)。
三、总结
快速排序的性能是不稳定的，快速排序的性能和划分的子数组的长度密切相关。
比如数组的长度为n，可以划分为1和n-1两个子数组。
在递归的时候又向n-1的集合中递归，这种是最坏的情况，时间复杂度为O(n2)。
在代码中引入了随机化来加速这个过程，实际的时间代价为期望的O(n)。
