Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

215. 数组中的第K个最大元素 #49

Open
webVueBlog opened this issue Sep 12, 2022 · 0 comments
Open

215. 数组中的第K个最大元素 #49

webVueBlog opened this issue Sep 12, 2022 · 0 comments

Comments

@webVueBlog
Copy link
Owner

215. 数组中的第K个最大元素

Description

Difficulty: 中等

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

给定整数数组 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 <= 105
  • -104 <= nums[i] <= 104

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
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant