# 215. 数组中的第 K 个最大元素
# 题目描述
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4 说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
# 我的回答
# 解法一
# 时空复杂度
时间复杂度：O(nlogn) 排序复杂度
空间复杂度: O(n) n 是数字种数
一行代码解决
var findKthLargest = function (nums, k) {
return [...nums].sort((a, b) => b - a)[k - 1]
};
# 解法二
# 时空复杂度
时间复杂度：O(n) 数字的种数
空间复杂度: O(1) 原地排序
const swap = (arr, l, r) => ([arr[l], arr[r]] = [arr[r], arr[l]])
function quickSelect(nums, left, right, k) {
const random = Math.floor(Math.random() * (right - left + 1)) + left
swap(nums, right, random)
// 将i作为挡板
let i = left
let j = left
while (j < right) {
if (nums[j] < nums[right]) swap(nums, i++, j)
j++
}
swap(nums, i, j)
// 交换完毕,num[i]就是 第i小的数
// 即 第i大的数 技术 right - i +1
if (k == right - i + 1) return nums[i]
// top K 在左边
if (k < right - i + 1) return quickSelect(nums, i + 1, right, k)
// top K 在右边
return quickSelect(nums, left, i - 1, k - (right - i + 1))
}
var findKthLargest = function (nums, k) {
return quickSelect(nums, 0, nums.length - 1, k)
};