复杂度为n的topk问题
2018-11-21 本文已影响11人
Aleph_Zheng
思想：类似快排的分治思想，把数组每次都按照pivot分左右两边，当pivotIdx等于我们的k-1时，这个pivot就是我们要找的topK，否则则从左或右数组再次遍历。直到数组只剩下一个元素为止。
<html>
<script>
//resolve topK
function topk(arr,k){
//终止条件，数组只剩下一个时
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++){
//小于等于为了保证排序稳定
if(arr[i]<=pivot){
left.push(arr[i])
}else{
right.push(arr[i])
}
}
//左数组的长度即为pivot的Index
let pivotIdx = left.length
if(pivotIdx === k-1 ){
return pivot
}else if(left.length>=k){
//这里记得要return这个函数，否则无法接受到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
/*
时间复杂度分析
每次都要遍历数组的一半（左半和右半），虽然左右数组大小可能不同，但都是类似分半了
所以遍历次数为n,n/2,n/4...1
很显然是一个等比数组，
s=n+n/2+n/4+...1
用点高中的小技巧
2s=2n+n+n/2+..2
2s-s=2n-1
s=2n-1
所以这个时间复杂度是n
*/
</script>
</html>
