【进阶篇 - Day 54】 2020-12-24 - 215. 数组中的第 K 个最大元素

题目描述

入选理由

• 经典第 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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的回答

https://github.com/leetcode-pp/91alg-2/issues/84#issuecomment-751160728

解法一

时空复杂度

时间复杂度：O(nlogn)

空间复杂度: O(1)

api boy 调用就完事了

var findKthLargest = function (nums, k) {
    nums = nums.sort((a, b) => b - a)
    return nums[k - 1]
};

解法二

时空复杂度

时间复杂度：O(n)

空间复杂度: O(1)

复习下快速选择 令人头秃

let swap = (nums, a, b) => [nums[a], nums[b]] = [nums[b], nums[a]]
let quicklySelect = function (nums, k, start = 0, end = nums.length - 1) {
    if (start > end) return
    let i = start
    let j = start
    let index = Math.floor(Math.random() * (end - start + 1)) + start
    swap(nums, end, index)
    while (j < end) {
        if (nums[j] > nums[end]) {
            swap(nums, i, j)
            i++
        }
        j++
    }
    swap(nums, j, i)
    if (i === (k - 1)) return nums[i]
    if (i < (k - 1)) return quicklySelect(nums, k, i + 1, end)
    if (i > (k - 1)) return quicklySelect(nums, k, start, i - 1)
}
var findKthLargest = function (nums, k) {
    return quicklySelect(nums, k)
};

解法三

时空复杂度

时间复杂度：O(nlogk)

空间复杂度: O(1)

堆排序 先占个位置

参考回答