LeetCode 215 Kth Largest Element in an Array 数组中的第K大元素

描述

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

You must solve it in O(n) time complexity.

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/kth-largest-element-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

/**
 * 快速选择算法
 * 利用实现快排的思想，每次partition操作，pivot元素的位置总是可以被确认
 * 先将数组对于pivot逆序
 * 逆序之后，pivot的位置已经确定，此时分为两种情况
 * 1. k在基准值右边，k比pIndex小，递归右区间，右区间没有pivot和left的元素，因此查找所有数组中的第k大元素，变成了查找右区间的第k-left.length-1大的元素
 * 2. k在基准值左右，k比pIndex大，递归左区间，第k大元素在左区间依然是第k大元素，此时k位置不变
 * 3. k在基准值位置上，此时返回pivot即可
 * 这样做的好处就是把原来的快排需要递归两个区间，变成只递归一个区间, 同时引入随机化，避免有序数组的情况下时间复杂度为O(n²)
 * 最终时间复杂度为O(n)
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
    return quickSelect(nums, k - 1)
};


const quickSelect = (nums, kIndex, result) => {
    if (result != null) return result // 递归出口。pivot刚好落在第k大的元素上
    const left = []
    const right = []
    const pivot = nums.splice(Math.floor(Math.random() * nums.length), 1)[0]
    let pivotIndex = 0 // 排序后，pivot的索引位置
    // 基于pivot逆序
    for (let i = 0; i < nums.length; i++) {
        const v = nums[i]
        if (v > pivot) {
            left.push(v)
            pivotIndex++
            continue
        }
        right.push(v)
    }
    if (pivotIndex === kIndex) {
        return quickSelect(nums, kIndex, pivot)
    }

    // 逆序之后，分为两种情况
    // 1. k在基准值右边，k比pIndex小，递归右区间，右区间没有pivot和left的元素，因此查找所有数组中的第k大元素，变成了查找右区间的第k-left.length-1大的元素
    // 2. k在基准值左右，k比pIndex大，递归左区间，第k大元素在左区间依然是第k大元素，此时k位置不变
    return pivotIndex < kIndex ? quickSelect(right, kIndex - left.length - 1) : quickSelect(left, kIndex)
}

console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2))