1. 使用堆算法實(shí)現(xiàn)Top，時(shí)間復(fù)雜度為 O(LogN)

    function top(arr,comp){  
    if(arr.length == 0){return ;}  
    var i = arr.length / 2 | 0 ;  
    for(;i >= 0; i--){  
    if(comp(arr[i], arr[i * 2])){exch(arr, i, i*2);}  
    if(comp(arr[i], arr[i * 2 + 1])) {exch(arr, i, i*2 + 1);}  
    }  
    return arr[0];  
      
      
    }  
      
      
    function exch(arr,i,j){  
    var t = arr[i];  
    arr[i] = arr[j];  
    arr[j] = t;  
    }  

2. 調(diào)用K次堆實(shí)現(xiàn)，時(shí)間復(fù)雜度為 O(K * LogN)

    function topK(arr,n,comp){  
    if(!arr || arr.length == 0 || n <=0 || n > arr.length){  
    return -1;  
    }  
      
      
    var ret  = new Array();  
    for(var i = 0;i < n; i++){  
    var max = top(arr,comp);  
    ret.push(max);  
    arr.splice(0,1);  
    }  
    return ret;  
    }  

3.測試

    var ret = topK(new Array(16,22,91,0,51,44,23),3,function (a,b){return a < b;});  
    console.log(ret);  

標(biāo)簽：

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。