题目

题解

使用快速选择算法

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    let targetIndex = nums.length - k ;
    let l = 0;
    let r = nums.length - 1;
    while(l < r) {
        // 拿到快速排序函数返回当前的索引值，
        //  判断该索引在目标值的那一边
        let mid = quickSelect(nums, l, r);
        if(mid == targetIndex) {
            return nums[mid];
        } else if (mid < targetIndex) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return nums[l]
};
function quickSelect(nums, l, r) {
    let left = l;
    let right = r;
    let pivot = nums[l];
    while(left < right) {
        // 当右值大于比较值
        while(left < right && nums[right] >= pivot) {
            right --;
        }
        // 右值小与比较值
        nums[left] = nums[right];
        // 当左值小与比较值
        while( left < right && nums[left] <= pivot) {
            left++;
        }
        // 当左值大于比较值
        nums[right] = nums[left];
    }
    // 将比较值放到中间位置
    nums[left] = pivot;
    // 将其索引返回
    return left;
}