思想：類似快排的分治思想川队，把數(shù)組每次都按照pivot分左右兩邊漱挎，當(dāng)pivotIdx等于我們的k-1時系枪，這個pivot就是我們要找的topK，否則則從左或右數(shù)組再次遍歷磕谅。直到數(shù)組只剩下一個元素為止私爷。
<html>
<script>
//resolve topK
function topk(arr,k){
//終止條件，數(shù)組只剩下一個時
if(arr.length===1){
return arr[0]
}
let pivot = arr[arr.length-1]
let left = []
let right = []
for(let i=0;i<arr.length-1;i++){
//小于等于為了保證排序穩(wěn)定
if(arr[i]<=pivot){
left.push(arr[i])
}else{
right.push(arr[i])
}
}
//左數(shù)組的長度即為pivot的Index
let pivotIdx = left.length
if(pivotIdx === k-1 ){
return pivot
}else if(left.length>=k){
//這里記得要return這個函數(shù)膊夹，否則無法接受到return值
return topk(left,k)
}else{
return topk(right,k-left.length-1)
}
}
let k = topk([4,2,5,12,-1,2,5,6,-5,3],3)
console.log('k',k);//2
/*
時間復(fù)雜度分析
每次都要遍歷數(shù)組的一半（左半和右半）衬浑，雖然左右數(shù)組大小可能不同，但都是類似分半了
所以遍歷次數(shù)為n,n/2,n/4...1
很顯然是一個等比數(shù)組放刨，
s=n+n/2+n/4+...1
用點(diǎn)高中的小技巧
2s=2n+n+n/2+..2
2s-s=2n-1
s=2n-1
所以這個時間復(fù)雜度是n
*/
</script>
</html>
