Ich habe kürzlich diesen Javascript-Code auf StackOverflow gesehen, um zwei Arrays zusammenzuführen und Duplikate zu entfernen:
Array.prototype.unique = function() {
var a = this.concat();
for(var i=0; i<a.length; ++i) {
for(var j=i+1; j<a.length; ++j) {
if(a[i] === a[j])
a.splice(j--, 1);
}
}
return a;
};
var array1 = ["Vijendra","Singh"];
var array2 = ["Singh", "Shakya"];
var array3 = array1.concat(array2).unique();
Während dieser Code funktioniert, ist er schrecklich ineffizient ( O(n^2)
). Ihre Herausforderung besteht darin, einen Algorithmus mit weniger Komplexität zu erstellen.
Das Gewinnkriterium ist die Lösung mit der geringsten Komplexität , aber die Bindungen werden durch die kürzeste Länge der Zeichen unterbrochen.
Anforderungen :
Packen Sie Ihren gesamten Code in eine Funktion, die die folgenden Anforderungen für "Korrektheit" erfüllt:
- Eingabe: Zwei Arrays
- Ausgabe: Ein Array
- Führt Elemente beider Arrays zusammen. Jedes Element in einem der Eingabearrays muss sich im ausgegebenen Array befinden.
- Das ausgegebene Array sollte keine Duplikate enthalten.
- Bestellung spielt keine Rolle (im Gegensatz zum Original)
- Jede Sprache zählt
- Verwenden Sie die Array-Funktionen der Standardbibliothek nicht zum Erkennen von Eindeutigkeiten oder zum Zusammenführen von Mengen / Arrays (obwohl andere Elemente aus der Standardbibliothek in Ordnung sind). Lassen Sie mich unterscheiden, dass die Array-Verkettung in Ordnung ist, Funktionen, die bereits alle oben genannten Funktionen ausführen, jedoch nicht.
[1, 2, 2, 3]
und[2, 3, 4]
zurückkehren[1, 2, 2, 3, 4]
oder[1, 2, 3, 4]
?Antworten:
Perl
27 Zeichen
Einfacher Perl Hack
Ich bin mir sicher, jemand könnte das einzeilen .. und damit (Danke Dom Hastings)
quelle
sub x{$_{$_}++for@_;keys%_}
(falls es sich um ein Unentschieden handelt!) Und verwenden als:z((1,2,3,4),(2,3,4,5,6))
JavaScript O (N)
13112411692 (86?)Golf Version:
Vom Menschen lesbare Golfversion:
Ich könnte
concat
so verwenden und es in 86 Zeichen tun:Ich bin mir aber nicht sicher, ob es immer noch O (N) ist, basierend auf diesem JsPerf: http://jsperf.com/unique-array-merging-concat-vs-looping, da die Concat-Version mit kleineren Arrays etwas schneller ist, mit aber langsamer größere Arrays (Chrome 31 OSX).
Tun Sie dies in der Praxis (Golf ist voll von schlechten Praktiken):
Ich bin nicht besonders komplex im Rechnen, aber ich glaube, das ist es
O(N)
. Würde mich freuen, wenn jemand das klären könnte.Bearbeiten: Hier ist eine Version, die eine beliebige Anzahl von Arrays aufnimmt und zusammenführt.
quelle
O(N)
.O(A*B)
(Nicht verwenden,N
weil es verwirrend ist). Es wäre, wenn jedes Eingabearray (jedesA
) die gleiche Anzahl von Elementen (B
) hätte, wie es tatsächlich ist. DiesO(SUM(B) FOR ALL A)
kann so umgeschrieben werdenO(N)
,N
als würde die Anzahl der Elemente aller Array-Eingaben definiert.Python 2.7, 38 Zeichen
Sollte O (N) sein und eine gute Hash-Funktion annehmen.
Wasis 8-Zeichen-
set
Implementierung ist besser, wenn Sie nicht glauben, dass sie gegen die Regeln verstößt.quelle
PHP,
69/4268/41 ZeichenEinschließlich der Funktionsdeklaration sind dies 68 Zeichen:
Ohne die Funktionsdeklaration sind es 41 Zeichen:
quelle
Ein Weg in Ruby
Um die oben beschriebenen Regeln einzuhalten, würde ich eine ähnliche Strategie wie die JavaScript-Lösung verwenden und einen Hash als Vermittler verwenden.
Im Wesentlichen sind dies die Schritte, die ich in der obigen Zeile durchlaufe.
merged_arr
, die das Ergebnis enthältObject#tap
diese Option, um den Hash (auf denhash
imtap
Block verwiesen wird ) zu füllen und für die nachfolgende Methodenverkettung zurückzugebenarr1
undarr2
in ein einzelnes, unverarbeitetes Arrayel
im verketteten Array den Wertel
ein,hash[el]
wennhash[el]
derzeit kein Wert von vorhanden ist. Das Merken hier (hash[el] ||= el
) sichert die Eindeutigkeit der Elemente.Dies sollte
O(n)
rechtzeitig ausgeführt werden. Bitte lassen Sie mich wissen, wenn ich ungenaue Angaben gemacht habe oder die obige Antwort aus Gründen der Effizienz oder Lesbarkeit verbessern kann.Mögliche Verbesserungen
Die Verwendung von Memoization ist wahrscheinlich unnötig, da die Schlüssel für den Hash eindeutig und die Werte irrelevant sein werden. Dies ist also ausreichend:
Ich liebe es wirklich
Object#tap
, aber wir können das gleiche Ergebnis erzielen mitEnumerable#reduce
:Sie könnten sogar verwenden
Enumberable#map
:Wie ich es in der Praxis machen würde
Abgesehen davon würde ich, wenn ich gebeten würde, zwei Arrays zusammenzuführen
arr1
undarr2
das Ergebnismerged_arr
eindeutige Elemente enthält und jede mir zur Verfügung stehende Ruby-Methode verwenden könnte, einfach den Operator set union verwenden, mit dem genau dieses Problem gelöst werden soll:Ein kurzer Blick auf die Quelle von
Array#|
scheint jedoch zu bestätigen, dass die Verwendung eines Hash als Intermediär die akzeptable Lösung für die Durchführung einer eindeutigen Zusammenführung zwischen zwei Arrays ist.quelle
Eine Funktion, die n Arrays benötigt, könnte die folgende sein:
Golf, ich denke, das sollte funktionieren (117 Zeichen)
Aktualisieren Wenn Sie den Originaltyp beibehalten möchten, können Sie dies tun
oder golfen 149:
Dies kann immer noch einige Zweifel aufkommen lassen, wenn Sie unterscheiden möchten
123
und'123'
, dann würde dies nicht funktionieren.quelle
O(N)
)?m([1,2,3,4,5],[2,3,4,5,6],[2,3,4,5,6,7])
wird["1", "2", "3", "4", "5", "6", "7"]
Python, 46
Oder einfach mit der Set-Operation
Python, 8
quelle
Perl
23 Bytes, wenn wir nur den Codeblock innerhalb des Unterprogramms zählen. Könnte 21 sein, wenn das Überschreiben globaler Werte zulässig ist (wird
my
aus dem Code entfernt). Es gibt Elemente in zufälliger Reihenfolge zurück, da die Reihenfolge keine Rolle spielt. Die Komplexität ist im Durchschnitt O (N) (hängt von der Anzahl der Hash-Kollisionen ab, ist jedoch eher selten - im schlimmsten Fall kann es O (N 2 ) sein (dies sollte jedoch nicht passieren, da Perl pathologische Hashes erkennen kann , und ändert den Startwert für die Hash-Funktion, wenn ein solches Verhalten erkannt wird)).Ausgabe (zeigt auch Zufälligkeit):
quelle
Fortran:
282252233213Golf Version:
Was nicht nur unendlich besser aussieht, sondern tatsächlich (in seiner Golfform) eine zu lange Zeile mit der für den Menschen lesbaren Form kompiliert:
Dies sollte sein ,
O(n)
wie ich kopierea
inc
und dann jeden überprüfenb
gegen allec
. Der letzte Schritt ist, den Müll zu beseitigen, derc
enthalten sein wird, da er nicht initialisiert ist.quelle
Mathematica 10 Zeichen
Beispiel:
Mathematica2 43 Zeichen
quelle
Tally[Join[a, b]][[;; , 1]]
wäre auch Betrug ;-) Übrigens könnten Sie Zeichen sparen, indem Sie Variablen mit einem Buchstaben verwenden.Javascript 86
Golf Version:
Lesbare Version:
quelle
m([1,0,0,0,0],[0,1,0])
zurück[1]
.h[v]=v
zuh[v]=1
.JavaScript 60
Ich benutze ES6 Generator.
Das Folgende kann mit Googles Traceur REPL getestet werden .
quelle
Wenn Sie nach einer JavaScript-basierten Implementierung suchen, die sich auf die zugrunde liegenden Objekte stützt, um effizient zu sein, hätte ich nur Set verwendet. In der Regel behandelt das Set-Objekt in einer Implementierung beim Einfügen eindeutige Objekte mit einer Art binärer Suchindizierung. Ich weiß, dass es sich in Java um eine
log(n)
Suche handelt, bei der eine binäre Suche verwendet wird, da kein Satz ein einzelnes Objekt mehr als einmal enthalten kann.Ich habe zwar keine Ahnung, ob dies auch für Javascript zutrifft, aber für eine
n*log(n)
Implementierung kann etwas so Einfaches wie das folgende Snippet ausreichen :JavaScript , 61 Bytes
Probieren Sie es online!
Wenn das obige Snippet verwendet
a = [1,2,3]
undb = [1,2,3,4,5,6]
danns=[1,2,3,4,5,6]
.Wenn Sie die Komplexität der wissen
Set.add(Object)
Funktion in JavaScript lassen Sie mich wissen, ist die Komplexität dieser ,n + n * f(O)
wof(O)
die Komplexität ists.add(O)
.quelle
APL (Dyalog Unicode) , O (N), 28 Byte
Anonyme stillschweigende Infix-Funktion.
Probieren Sie es online!
,
verketten die Argumente; AUF)(
…)
Wenden darauf die folgende anonyme stillschweigende Funktion an; O (1)⍳⍨
Indizes selfie (Indizes des ersten Auftretens jedes Elements im gesamten Array); AUF)=
Element für Element vergleichen mit; AUF):⍳∘≢
Indizes der Länge des Arrays; AUF)(/⍨)
benutze das um zu filtern; AUF):⊢
das unveränderte Argument; O (1)O (N + 1 + N + N + N + N + 1) = O (N)
quelle
JavaScript, 131 Zeichen
quelle
PHP rund 28 Zeichen [ohne die Beispiel-Array-Variablen und die Ergebnisvariable].
$ array1 = array (1, 2, 3); $ array2 = array (3, 4, 5);
$ result = array_merge ($ array1, $ array2);
quelle