Was ist der effizienteste Weg, eine Anordnung auf dem Inhalt eines anderen Array anhand von Filtern?
-
03-07-2019 - |
Frage
Sagen, ich habe zwei Arrays, Gegenstände und removeItems und ich wollte in removeItems gefunden alle Werte aus den Gegenständen entfernt werden.
Der Brute-Force-Mechanismus wäre wahrscheinlich:
var animals = ["cow","dog","frog","cat","whale","salmon","zebra","tuna"];
var nonMammals = ["salmon","frog","tuna","spider"];
var mammals = [];
var isMammal;
for(var i=0;i<animals.length;i++){
isMammal = true;
for(var j=0;j<nonMammals;j++){
if(nonMammals[j] === animals[i]){
isMammal = false;
break;
}
}
if(isMammal){
mammals.push(animals[i]);
}
}
Dies ist, was? O (N ^ 2)? Gibt es eine effizientere Art und Weise?
Lösung
Das ist eigentlich O(M * N)
.
Wahrscheinlich könnte man besser machen die animals
Array Sortierung zuerst, dann eine binäre Suche zu tun. Sie werden in der Lage zu O(N * log N)
zu reduzieren -. Gut, das ist, wenn log N < M
sowieso
Wie auch immer, wenn Sie mit JS arbeiten und das läuft clientseitige, dann versucht nur zu minimaler Menge von Daten zu halten oder ihr Browser mit jeder Anfrage an Sie schreit.
Andere Tipps
Im Grunde, was Sie tun möchten, ist effizient die eingestellte Differenz S \ T. Die Berechnung (asymptotisch) schnellste Weg, ich weiß, ist T in eine hashmap zu setzen (das macht | T | Stufen) und gehen jeweils in S s ( das macht | S | Stufen) Überprüfung, ob s in T (die O (1)). So erhalten Sie auf O (| T | + | S |). Schritte