JS 笔试题——数组中的第K个最大元素

题目：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

分析：

• 先降序排序
• 再找到第 个元素，返回即可

排序算法这里实现两种：插入排序，快速排序

完整代码：

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    // 先使用插入排序
    insertSort(nums);
    let ans = nums.splice(k - 1, 1);
    return ans;
};

var insertSort = function(nums) {
    let j;
    for (let i = 1; i < nums.length; i++) {
        let cur = nums[i];
        for (j = i; j >= 1; j--) {
            if (nums[j - 1] < cur) {
                nums[j] = nums[j - 1];
            } else {
                break;
            }
        }
        nums[j] = cur;
    }
}

也可以使用快速排序方法：

var quickSort = function(nums) {
    let sort = ((arr, left, right)=>{
        let mid = Math.floor((left + right) / 2);
        let value = nums[mid];
        let i = left, j = right;
        // i 向右走, j 向左走
        while (i < j) {
            for (; !(i >= mid || value > nums[i]); i++) {}
            if (i < mid) {
                nums[mid] = nums[i];
                mid = i;
            }

            for (; !(j <= mid || nums[j] > value); --j) {}
            if (j > mid) {
                nums[mid] = nums[j]
                mid = j;
            }
        }
        nums[mid] = value;

        if (mid - left > 1) {
            sort(nums, left, mid - 1);
        }

        if (right - mid > 1) {
            sort(nums, mid + 1, right);
        }
    });
    sort(nums, 0, nums.length);
}