Javascript：將解決方案更改爲O（n log n）

Question

以下是我在學習Javascript時遇到的問題的解決方案： - 問題： - 查找他參加過的擊球手對陣球隊的最高平均得分比賽。 下面是取得了對他在比賽中已經打進了球隊的運行： -

[  
    ["Srilanka", 23], 
    ["Srilanka", 230], 
    ["Pakistan", 127], 
    ["India", 3], 
    ["India", 71], 
    ["Australia", 310], 
    ["India", 22], 
    ["Pakistan", 1] 
] 

我曾與寫入的解決方案代碼爲： -

function getHighscoreAaverage (input) { 
try { 
    var matches = JSON.parse(input); 
} catch(e) { 
    console.error('Error parsing input string...'); 
    return ''; 
} 

var average_runs = []; 
var high_average = 0; 
var high_average_country = ''; 

for (var i = 0; i< matches.length; i++) { 

    if(typeof average_runs[matches[i][0]] === "undefined") { 
     average_runs[matches[i][0]] = { 
      "total": 0, 
      "count": 0, 
      "average": 0 
     } 
    } 

    average_runs[ matches[i][0] ]["total"] += matches[i][1]; 
    average_runs[ matches[i][0] ]["count"] += 1; 
    average_runs[ matches[i][0] ]["average"] = average_runs[matches[i][0]]["total"]/average_runs[matches[i][0]]["count"]; 

} 

for (country in average_runs) { 
    if(average_runs[country]["average"] > high_average){ 
     high_average = average_runs[country]["average"]; 
     high_average_country = country; 
    } 
} 


return high_average_country; 
} 
getHighscoreAaverage ('[ ["Srilanka", 23], ["Srilanka", 230], ["Pakistan", 127], ["India", 3], ["India", 71], ["Australia", 310], ["India", 22], ["Pakistan", 1]]'); 

我想檢查與其他程序員，這是否代碼可以進一步優化。我想提高我的編碼水平，任何對此的幫助將深表感謝。

建議的代碼： - 注意：下面的代碼不能給出正確的答案。

function getHighscoreAaverage (input) { 
    try { 
     var matches = JSON.parse(input); 
    } catch(e) { 
     console.error('Error parsing input string...'); 
     return ''; 
    } 

    var average_runs = []; 
    var high_average = 0; 
    var high_average_country = ''; 

    for (var i = 0; i< matches.length; i++) { 

     if(typeof average_runs[matches[i][0]] === "undefined") { 
      average_runs[matches[i][0]] = { 
       "total": 0, 
       "count": 0, 
       "average": 0 
      } 
     } 

     average_runs[ matches[i][0] ]["total"] += matches[i][1]; 
     average_runs[ matches[i][0] ]["count"] += 1; 
     average_runs[ matches[i][0] ]["average"] = average_runs[matches[i][0]]["total"]/average_runs[matches[i][0]]["count"]; 

     if(average_runs[matches[i][0]]["average"] > high_average){ 
      high_average = average_runs[matches[i][0]]["average"]; 
      high_average_country = matches[i][0]; 
     } 
    } 

    return high_average_country; 
} 

Answer 1

firtsly，注意，你原來的解決方案是O（n）（假設實現是足夠聰明），所以爲什麼你要一個O（nlogn）的解決方案？

無論如何，爲了比較到位的最高avarage，我們必須首先排序項值，使運行avarages單調......

var input = [  
 
    ["Srilanka", 23], 
 
    ["Srilanka", 230], 
 
    ["Pakistan", 127], 
 
    ["India", 3], 
 
    ["India", 71], 
 
    ["Australia", 310], 
 
    ["India", 22], 
 
    ["Pakistan", 1] 
 
]; 
 

 
var result; 
 

 
input 
 
    .sort(function(a,b) { return a[1] - b[1]; }) 
 
    .reduce(function(a,n){ 
 
    if(!a[n[0]]) a[n[0]] = { count: 0, total: 0 }; 
 
    
 
    var entry = a[n[0]]; 
 
    
 
    entry.count ++; 
 
    entry.total += n[1]; 
 
    
 
    var avg = entry.total/entry.count; 
 
    
 
    if(!result || result.avg < avg) 
 
     result = { name: n[0], avg: avg }; 
 
    
 
    return a; 
 
    },{}); 
 

 
console.log(result);

只爲您的信息，在這裏就是我想實現它（有下劃線的幫助下），這樣的：

var input = [  
 
    ["Srilanka", 23], 
 
    ["Srilanka", 230], 
 
    ["Pakistan", 127], 
 
    ["India", 3], 
 
    ["India", 71], 
 
    ["Australia", 310], 
 
    ["India", 22], 
 
    ["Pakistan", 1] 
 
]; 
 

 
var highest_avarage = _.chain(input) 
 
    .groupBy(entry => entry[0]) 
 
    .map((totals,name) => ({ name: name, avg: totals.reduce((a,b)=>(a+b[1]), 0)/totals.length })) 
 
    .max(entry => entry.avg); 
 

 
console.log(highest_avarage);

<script src="http://underscorejs.org/underscore-min.js"></script>