215. Kth Largest Element in an Array

source: https://leetcode.com/problems/kth-largest-element-in-an-array/

Question

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.

思路

这题的主要思路还是去微调排序算法，在排到K的时候，就返回。

堆排序

先从无子节点遍历，自底向上创建Max Heap。

然后一个个把根节点，which is the maximum, 置换下去，同时缩小heapify的范围。

/**
 * heap sort
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
    /**
     * swap value in arr
     * @param i1 
     * @param i2 
     */
    const swap = (i1, i2) => {
        const v = nums[i1];
        nums[i1] = nums[i2];
        nums[i2] = v;
    };

    /**
     * To heapify a subtree rooted with node
     * @param {number} n size of heap
     * @param {number} i an index in arr[]
     */
    const heapify = (n, i) => {
        const l = 2 * i + 1; // left = 2*i + 1
        const r = 2 * i + 2; // right = 2*i + 2
        let largest = i; // Initialize largest as root
        // If left child is larger than root
        if (l < n && nums[l] > nums[largest]) largest = l;
        // If right child is larger than largest so far
        if (r < n && nums[r] > nums[largest]) largest = r;
        // If largest is not root
        if (largest !== i) {
            swap(i, largest);
            // Recursively heapify the affected sub-tree
            heapify(n, largest);
        }
    };

    // Build heap (rearrange array)
    for (let i = Math.floor(nums.length / 2) - 1; i >= 0; i--) heapify(nums.length, i);

    // One by one extract an element from heap
    for (let i = nums.length - 1; i >= nums.length - k; i--) {
        // Move current root to end
        swap(0, i);
        // call max heapify on the reduced heap
        heapify(i, 0);
    }
    return nums[nums.length - k];
};

快排

快排时对于那个pivot，是可以确定index位置的，当index是目标时，即可返回。

/**
 * quick sort
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
    const quickSort = (arr, i) => {
        if (!arr.length) return;
        const pivot = arr.pop();
        const left = arr.filter(v => v < pivot);
        const right = arr.filter(v => v >= pivot);
        const index = i + left.length;
        if (index === nums.length - k + 1) return pivot;
        const i1 = quickSort(right, i + left.length + 1);
        if (i1 !== undefined) return i1;
        const i2 = quickSort(left, i);
        if (i2 !== undefined) return i2;
    };
    return quickSort(nums, 0);
};

End

其实这题就是考排序算法，就是换了一种方式。

类似的题目还有973题，也是通过排序算法，尽量少的去排序。