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

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
    // 基于桶排序
    const sorted = bucketSort(nums)
    return sorted[k - 1]
};

/**
 * 桶排序，时间复杂度O(n)
 * @param {number[]} arr 
 */
function bucketSort(arr) {
    if (!arr.length) {
        return []
    }
    // 1.确定桶容量
    const bucketSize = arr.length

    // 2.确定最小值最大值
    const min = Math.min(...arr)
    const max = Math.max(...arr)

    // 3.确定桶数量
    const bucketCount = Math.floor((max - min) / bucketSize) + 1
    const buckets = new Array(bucketCount).fill(0).map(() => [])

    // 4.确定每个元素放到哪个桶
    for (let i = 0; i < arr.length; i++) {
        let pos = Math.floor((arr[i] - min) / bucketSize)
        buckets[pos].push(arr[i])
    }

    // 5.对每个桶进行排序，这里升序
    for (let i = 0; i < buckets.length; i++) {
        buckets[i].sort((a, b) => a - b)
    }

    // 6.合并桶
    let res = []
    for (let i = 0; i < buckets.length; i++) {
        res = res.concat(buckets[i])
    }

    // 这里结果要降序
    return res.reverse()
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
    // 基于快速排序
    // 我们知道快速排序基准值q将数组a[l...r]划分成左右两个子数组，a[l...q-1]和a[q+1...r]
    // 每次划分都能确定基准值q的最终位置，所以我们只需要在某次划分的时候基准值q为倒数第k个下标的时候，我们就找到答案了。
    // q的下标小于nums.length-k时在基准值右边的数组找，大于nums.length-k时在左边的数组找

    // 定义区间[start, end]，在区间找目标数
    function search(start, end) {
        if (start > end) { // 递归结束条件
            return
        }

        // 取第一个数作为基数，然后把区间划分为左右两部分
        let x = nums[start]
        // 定义两根指针，把比基数小的放到左边，把比基数大的放到右边
        let i = start
        let j = end
        while (i < j) {
            // 一定是j先移动，遇到比基数小的元素就停止
            while (i < j && nums[j] >= x) {
                j--
            }
            // 然后把元素值赋给i
            nums[i] = nums[j]

            // 然后到i移动，遇到比基数大的元素就停止
            while (i < j && nums[i] <= x) {
                i++
            }
            // 然后把元素值赋给j
            nums[j] = nums[i]
        }
        // 最后i==j，这个位置就是基数的下标
        let index = i // 基数的下标
        nums[index] = x

        // 第k大数就是倒数第k个元素
        if (index === nums.length - k) {
            return nums[index]
        } else if (index < nums.length - k) { // q小了，就往右边找
            return search(index + 1, end)
        } else if (index > nums.length - k) { // q大了，就往左边找
            return search(start, index - 1)
        }
    }

    return search(0, nums.length - 1)
};

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