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

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

• 库函数

/**
 *
 * @complex T(nlogn)/S(1);
 * @param {number[]} nums
 * @param {number} k
 * @return {*}  {number}
 */
function findKthLargest(nums: number[], k: number): number {
    nums.sort((a, b) => b - a);
    return nums[k - 1];
};

• 堆排序

/**
 *
 * @complex T(nlogn)/S(logn)[栈空间]
 * @param {number[]} nums
 * @param {number} k
 * @return {*}  {number}
 */
function findKthLargest(nums: number[], k: number): number {
    heapSort(nums, k);
    return nums[nums.length - k];
};

function heapSort(nums: number[], k: number = -1): void {
    // build heap
    for (let lastIndex: number = nums.length >> 1; lastIndex >= 0; --lastIndex) {
        maxHeapify(nums, lastIndex, nums.length);
    }
    // heap sort
    for (let lastIndex: number = nums.length - 1; lastIndex >= 0 && k--; --lastIndex) {
        [nums[0], nums[lastIndex]] = [nums[lastIndex], nums[0]];
        maxHeapify(nums, 0, lastIndex);
    }
}
function maxHeapify(nums: number[], i: number, length: number): void {

    for (let j = i * 2 + 1; j < length; j = i * 2 + 1) {
        if (j + 1 < length && nums[j] < nums[j + 1]) {
            ++j;
        }
        if (nums[i] >= nums[j]) {
            return;
        }
        [nums[i], nums[j],] = [nums[j], nums[i]];
        i = j;
    }

}