215. 数组中的第K个最大元素 (opens new window)

Description

Difficulty: 中等

Related Topics: 数组 (opens new window), 分治 (opens new window), 快速选择 (opens new window), 排序 (opens new window), 堆（优先队列） (opens new window)

给定整数数组 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 <= nums.length <= 10⁵
• -10⁴ <= nums[i] <= 10⁴

Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
// 数组排序，取第 k 个数
// var findKthLargest = function (nums, k) {
//     nums.sort((a, b) => b - a).slice(0, k)
//     return nums[k - 1]
// };

// 构造前 k 个最大元素小顶堆，取堆顶
// 从数组中取出 k 个元素构造一个小顶堆，然后将其余元素与小顶堆对比，如果大于堆顶则替换堆顶，然后堆化，所有元素遍历完成后，堆中的堆顶即为第 k 个最大值
var findKthLargest = function (nums, k) {
    let heap = [,], i = 0
    while (i < k) {
        heap.push(nums[i++])
    }
    buildHeap(heap, k)

    for (let i = k; i < nums.length; i++) {
        if (heap[1] < nums[i]) {
            heap[1] = nums[i]
            heapify(heap, k, 1)
        }
    }
    return heap[1]
};

let buildHeap = (arr, k) => {
    if (k === 1) return
    for (let i = Math.floor(k/2); i>=1; i--) {
        heapify(arr, k, i)
    }
}

let heapify = (arr, k, i) => {
    while(true) {
        let minIndex = i
        if (2*i <= k && arr[2*i] < arr[i]) {
            minIndex = 2*i
        }
        if (2*i+1 <= k && arr[2*i+1] <arr[minIndex]) {
            minIndex = 2*i + 1
        }
        if (minIndex !== i) {
            swap(arr, i, minIndex)
            i = minIndex
        } else {
            break
        }
    }
}

let swap = (arr, i, j) => {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}