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

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

难度：中等

原题

解法

没太明白为什么这道题的难度是中等，可能是直觉想出来的解法的复杂度并不是最优的，看到题目的题解也确实提了这点，还有更优的方法

解法一：排序

const findKthLargest = function(nums, k) {
    nums.sort((a, b) => b - a);
    return nums[k - 1];
}

复杂度分析：

• 时间复杂度O(NlogN)
• 空间复杂度O(1)

解法二：使用 partition 操作定位到最终排定以后索引为 len - k 的那个元素

特别注意：随即化切分元素 这个可以看下别人的分析-方法二

const findKthLargest = function(nums, k) {
    let len = nums.length;
    let left = 0;
    let right = len - 1;

    // 转换一下，第 k 大元素的索引是 len - k
    let target = len - k;

    while(true) {
        let index = partition(nums, left, right);
        if (index === target) {
            return nums[index];
        }
        else if (index < target) {
            left = index + 1;
        }
        else {
            right = index - 1;
        }
    }
}

/**
 * 在数组 nums 的子区间 [left, right] 执行 partition 操作，返回 nums[left] 排序以后应该在的位置
 * 在遍历过程中保持循环不变量的语义
 * 1、[left + 1, j] < nums[left]
 * 2、(j, i] >= nums[left]
 *
 * @param nums
 * @param left
 * @param right
 * @return
 */
const partition = function(nums, left, right) {
    let pivot = nums[left];
    let j = left;
    for (let i = left + 1; i <= right; i++) {
        // 最最重要的其实就是这个 if 里面的操作了
        if (nums[i] < pivot) {
            // 小于 pivot 的元素都被交换到前面
            j++;
            swap(nums, j, i);
        }
    }

    // 在之前遍历的过程中，满足 [left + 1, j] < pivot，并且 [j, i] >= pivot
    swap(nums, j, left);
    // 交换以后 [left, j - 1] < pivot, nums[j] = pivot, [j + 1, right] >= pivot
    return j;
}

const swap = function(nums, index1, index2) {
    let temp = nums[index1];
    nums[index1] = nums[index2];
    nums[index2] = temp;
}