求出数组中第K大的数

我们可以用暴力循环来求解，但是如果想把时间复杂度降到O(n)，我们可以借用「快速排序」的思想，一次常规操作后，我们的基准值（pivot）会将数组分为两半，前一半是比pivot小的，后一半是比pivot大的。此时这个pivot所处的数组下标为index，那么这个pivot就是整个数组中「第index+1」小的值。同理，如果我们将比pivot大的放在pivot的前半段，把比pivot小的放在pivot的后半段，那么这个pivot其实就是第「index+1」大的值了。如果这个「index+1」刚好等于k，那么我们就可以直接返回这个pivot值，如果「index+1」大于k，说明我们要找的值在arr[0]到arr[index-1]这个前半段区间上，反之则在arr[index+1]-arr[arr.length - 1]这个后半段区间上，然后循环查找。

代码：

function findKMax(arr, k) {
    let len = arr.length;
    let index = quick(0, arr.length - 1, arr);
    while(index + 1 != k) {
        if(index + 1 > k) {
            index = quick(0, index - 1);
        } else {
            index = quick(index + 1, len -1)
        }
    }
    return arr[index];

}

// 一次常规操作，使得pivot前半段比它大，后半段比它小
function quick(start, end, arr) {
    if(start >= end) return;
    let left = start;
    let right = end - 1;
    let key = arr[end];
    while(left < right) {
        while(left < right && arr[left] > key) left++;
        while(left < right && arr[right] < key) right--;
        [arr[left], arr[right]] = [arr[right], arr[left]];
    }
    if(arr[left] <= key) {
        [arr[left], arr[end]] = [arr[end], arr[left]];
    } else {
        left++;
    }
    return left;
}