给定整数数组 nums 和整数 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
提示：
1 <= k <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(nums, k) {
};
解题1
Array.sort从大到小排序，并取值
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(nums, k) {
nums.sort((a, b) => b - a)
return nums[k - 1]
};
解题2
推排序
- 思路是维持一个单调递减堆stack
- 循环nums数组，
- 判断堆顶元素是否小于数组元素n，满足，则推入tmp中
- 直到stack为空或不满足上一步判断
- 如果stack的长度小于k，则推入n
- 如果stack的长度还小于k，并tmp有值，持续将tmp中的值填入stack
- 最后返回stack栈顶元素
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(nums, k) {
let stack = []
for (let i = 0; i < nums.length; i++) {
const n = nums[i], tmp = []
while(stack.length && stack[stack.length - 1] < n) {
tmp.push(stack.pop())
}
if (stack.length < k) stack.push(n)
while(tmp.length && stack.length < k) {
stack.push(tmp.pop())
}
}
return stack[stack.length - 1]
};
- 时间复杂度：O(NK)，N = nums.length，K = k
- 空间复杂度：O(K)
解题3
快速排序，从大到小，取数组下标k-1的元素，即为所求。
因为题目只要求第K大的数字，所以不需要全部排序，只需要比较左右分的下标pos和k-1的大小，对部分区间进行排序即可
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(nums, k) {
quickSort(0, nums.length - 1)
return nums[k-1]
function quickSort(left, right) {
if (left < right) {
let pos = partition(left, right)
if (pos < k-1) quickSort(pos + 1, right)
if (pos > k-1) quickSort(left, pos - 1)
}
}
function partition(left, right) {
const pivot = nums[right]
let i = left
for(let j = left; j < right; j++) {
if (nums[j] >= pivot) {
swap(i++, j)
}
}
swap(i, right)
return i
}
function swap(i, j) {
const tmp = nums[i]
nums[i] = nums[j]
nums[j] = tmp
}
};
