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>