解题1

Array.sort从大到小排序，并取值

复制
1/**
2 * @param {number[]} nums
3 * @param {number} k
4 * @return {number}
5 */
6var findKthLargest = function(nums, k) {
7    nums.sort((a, b) => b - a)
8    return nums[k - 1]
9};

解题2

推排序

1. 思路是维持一个单调递减堆stack
2. 循环nums数组，
3. 判断堆顶元素是否小于数组元素n，满足，则推入tmp中
4. 直到stack为空或不满足上一步判断
5. 如果stack的长度小于k，则推入n
6. 如果stack的长度还小于k，并tmp有值，持续将tmp中的值填入stack
7. 最后返回stack栈顶元素

复制
1/**
2 * @param {number[]} nums
3 * @param {number} k
4 * @return {number}
5 */
6var findKthLargest = function(nums, k) {
7    let stack = []
8
9    for (let i = 0; i < nums.length; i++) {
10        const n = nums[i], tmp = []
11        while(stack.length && stack[stack.length - 1] < n) {
12            tmp.push(stack.pop())
13        }
14        if (stack.length < k) stack.push(n)
15        while(tmp.length && stack.length < k) {
16            stack.push(tmp.pop())
17        }
18    }
19    return stack[stack.length - 1]
20};

• 时间复杂度：O(NK)，N = nums.length，K = k
• 空间复杂度：O(K)

解题3

快速排序，从大到小，取数组下标k-1的元素，即为所求。 因为题目只要求第K大的数字，所以不需要全部排序，只需要比较左右分的下标pos和k-1的大小，对部分区间进行排序即可

复制
1/**
2 * @param {number[]} nums
3 * @param {number} k
4 * @return {number}
5 */
6var findKthLargest = function(nums, k) {
7    quickSort(0, nums.length - 1)
8    return nums[k-1]
9
10    function quickSort(left, right) {
11        if (left < right) {
12            let pos = partition(left, right)
13            if (pos < k-1)  quickSort(pos + 1, right)
14            if (pos > k-1)  quickSort(left, pos - 1)
15        }
16    }
17
18    function partition(left, right) {
19        const pivot = nums[right]
20        let i = left
21        for(let j = left; j < right; j++) {
22            if (nums[j] >= pivot) {
23                swap(i++, j)
24            }
25        }
26        swap(i, right)
27
28        return i
29    }
30
31    function swap(i, j) {
32        const tmp = nums[i]
33        nums[i] = nums[j]
34        nums[j]  = tmp
35    }
36};