我们可以用暴力循环来求解，但是如果想把时间复杂度降到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;
}
