Javascript: Ändern Sie die Lösung zu O (n log n)

Question

Unten ist die Lösung für eine Frage, die ich beim Lernen kam Javascript: - Frage: - Finden Sie die höchsten durchschnittlichen Läufe gegen ein Team von einem Schlagmann erzielte er in gespielt hat Der Wettbewerb. Im Folgenden sind die erzielten Runs gegen die Mannschaften er im Turnier erzielt hat: -

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

Die Lösung code Ich war geschrieben hatte: -

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]]'); 

ich mit anderen Programmierern, ob dies überprüfen wollte Code kann weiter optimiert werden. Ich wollte mein Coding Level verbessern und jede Hilfe wird sehr geschätzt.

Vorgeschlagener Code: - Hinweis: unter Code gibt nicht die richtige Antwort.

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, beachten Sie, dass Ihre ursprüngliche Lösung O (n) ist (vorausgesetzt, die Umsetzung intelligent genug ist), so warum wollen Sie eine O (n log n) Lösung?

sowieso, um den höchsten Durchschnitt an seinem Platz zu vergleichen, müssen wir zuerst sortiert nach Einzelteilwert machen avarages monotone ...

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);

nur für Ihre Info laufen, hier ist, wie ich es (mit Hilfe von Unterstrich) implementieren würde, so etwas wie:

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>