返回一组数中最大的K个（JS实现）
浏览数：19 /
时间：2015年06月09日
第一次见到类似题目大约是在六年前吧。一道简单的ACM题，自己费半天劲用土方法得出结果，跟别人用堆排序求得结果的时间效率相差数倍，使得笔者第一次深切领略到算法的魅力。六年之后，再一次被人问到这道题，“堆排序”瞬间蹦入脑海。
不同的是，当时玩C，现在玩Java和JS，最熟的就是JS了，于是用JS把算法写了出来：
function topKMaxOfArr(k, arr){
function swap(a, b){
var t = arr[a];
arr[a] = arr[b];
arr[b] = t;
}
var i,j;
//只需循环k次
for(i=arr.length;i>arr.length-k;i--){
for(j=Math.floor(i/2)-1;j>=0;j--){
if(arr[j]<arr[2*j+1]){
swap(j, 2*j+1);
}
if(2*j+2<i && arr[j]<arr[2*j+2]){
swap(j, 2*j+2);
}
}
swap( i-1, 0 );
}
return arr.slice( arr.length - k );
}
//用法示例
var arr = [4,2,5,6,77,33,21,44,55,22], k=5;
topKMaxOfArr(k, arr);//返回数组[22, 33, 44, 55, 77]欢迎批评指正。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
