数组中的第K个最大元素

数组中的第K个最大元素

题目描述

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

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
解释：排序后数组结果[1,2,3,4,5,6], 取第二大的那个数就是 5

分析

• 这个题目直接想就是数组通过排序后获取倒数第k个数
• 这里我使用快速排序

代码

// 快速排序
function quicksort(nums, low, high) {
    let i;
    let j;
    let s;
    while (high > low) {
        i = low;
        j = high;
        s = nums[low];
        while (i < j) {
            while (nums[j] > s) {
                j--;
            }
            nums[i] = nums[j];
            while (s >= nums[i] && i < j) {
                i++;
            }
            nums[j] = nums[i];
        }
        nums[i] = s;
        quicksort(nums, low, i - 1);
        low = i + 1;
    }
    return nums;
}
var findKthLargest = function(nums, k) {
    const newNums = quicksort(nums, 0, nums.length - 1);
    return newNums[nums.length - k];
};