Array-Zusammenführung ohne Duplikate

15

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.
hkk
quelle
Wie sollen wir ein Array erstellen oder an dieses anhängen, ohne Array-Funktionen zu verwenden?
Emil Vikström
@ EmilVikström Siehe meine Bearbeitung. Ich habe gemeint, dass Sie keine Array-Eindeutigkeitsfunktionen verwenden können. Entschuldigung für die Unklarheit.
HKK
Wenn eines der Arrays Duplikate enthält, entfernen wir sie auch? Soll zum Beispiel fusionieren [1, 2, 2, 3]und [2, 3, 4]zurückkehren [1, 2, 2, 3, 4]oder [1, 2, 3, 4]?
OI
1
@OI Ja, das würde es zu einfach machen.
HKK
1
Darf ich fragen: Arrays von was ? Können wir einfach ganze Zahlen oder Zeichenketten annehmen oder müssen wir auch komplexere Dinge wie mehrstufige Objekte zulassen?
jawns317

Antworten:

8

Perl

27 Zeichen

Einfacher Perl Hack

my @vals = ();
push @vals, @arr1, @arr2;
my %out;
map { $out{$_}++ } @vals;
my @unique = keys %out;

Ich bin mir sicher, jemand könnte das einzeilen .. und damit (Danke Dom Hastings)

sub x{$_{$_}++for@_;keys%_}
Zach Leighton
quelle
1
"Verwenden Sie die Array-Funktionen der Standardbibliothek nicht zum Erkennen von Eindeutigkeiten (obwohl andere Elemente der Standardbibliothek in Ordnung sind)"
John Dvorak
1
Wie verstoße ich gegen diese Regel? Ich benutze keine einzigartigen Funktionen?
Zach Leighton
Wie funktioniert es dann? Entschuldigung, ich kann Perl nicht lesen. Wenn es die Schlüssel einer Hash-Map liest - gilt das als OK für diese Regel? Ich werde nicht wählen, bis ich überzeugt bin, dass es so ist.
John Dvorak
1
Es kombiniert die Arrays, durchläuft beide Schleifen und addiert zu einem Hash den Wert, dessen Schlüssel der aktuelle Wert in der Array-Schleife ist. Dann nimmt es die Schlüssel dieses Hashs, ich habe dies in einigen meiner Arbeiten verwendet. So wird [1,1,2,3,4,4] zu {1 => 2, 2 => 1, 3 => 1 , 4 => 2}
Zach Leighton
@ZachLeighton Sie können den Code auf 27 Zeichen mit verkürzen sub x{$_{$_}++for@_;keys%_}(falls es sich um ein Unentschieden handelt!) Und verwenden als:z((1,2,3,4),(2,3,4,5,6))
Dom Hastings
10

JavaScript O (N) 131 124 116 92 (86?)

Golf Version:

function m(i,x){h={};n=[];for(a=2;a--;i=x)i.map(function(b){h[b]=h[b]||n.push(b)});return n}

Vom Menschen lesbare Golfversion:

function m(i,x) {
   h = {}
   n = []
   for (a = 2; a--; i=x)
      i.map(function(b){
        h[b] = h[b] || n.push(b)
      })
   return n
}

Ich könnte concatso verwenden und es in 86 Zeichen tun:

function m(i,x){h={};n=[];i.concat(x).map(function(b){h[b]=h[b]||n.push(b)});return n}

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

function merge(a1, a2) {
   var hash = {};
   var arr = [];
   for (var i = 0; i < a1.length; i++) {
      if (hash[a1[i]] !== true) {
        hash[a1[i]] = true;
        arr[arr.length] = a1[i];
      }
   }
   for (var i = 0; i < a2.length; i++) {
      if (hash[a2[i]] !== true) {
        hash[a2[i]] = true;
        arr[arr.length] = a2[i];
      }
   }
   return arr;
}
console.log(merge([1,2,3,4,5],[1,2,3,4,5,6]));

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.

function merge() {
   var args = arguments;
   var hash = {};
   var arr = [];
   for (var i = 0; i < args.length; i++) {
      for (var j = 0; j < args[i].length; j++) {
        if (hash[args[i][j]] !== true) {
          arr[arr.length] = args[i][j];
          hash[args[i][j]] = true;
        }
      }
    }
   return arr;
}
console.log(merge([1,2,3,4,5],[1,2,3,4,5,6],[1,2,3,4,5,6,7],[1,2,3,4,5,6,7,8]));
George Reith
quelle
Dies ist fast genau das, was ich in ein paar Sekunden posten wollte :-( Ja, es wird die lineare Zeit amortisiert, wenn Hash-Tabellen mit einer konstanten amortisierten Zeit zum Einfügen und Suchen implementiert werden (was in vielen Sprachen üblich ist, weiß es nicht genau über JS)
Emil Vikström
@ EmilVikström Danke dafür, ich glaube JavaScript hat aber keinen Beweis dafür. Entschuldigung für die schnellen Finger, hat sich mit Kommentaren verlangsamt: P
George Reith
Dies ist ein großartiger Ansatz. Könnten Sie jedoch zusätzlich zu Ihrer gut formatierten Version auch eine Lösung im "Code-Golf" -Stil anbieten? Angesichts der Tatsache, dass dies von mehreren Menschen als der richtige Ansatz angesehen wurde, wird es wahrscheinlich ein Unentschieden geben O(N).
HKK
@ cloudcoder2000 Ok, ich wollte eine Vollversion drucken, da die Code-Golf-Version in der Praxis wahrscheinlich weniger effizient ist.
George Reith
1
@ cloudcoder2000 Sie sind nicht vollständig unabhängig, der schlimmste Fall ist also nicht O(A*B)(Nicht verwenden, Nweil es verwirrend ist). Es wäre, wenn jedes Eingabearray (jedes A) die gleiche Anzahl von Elementen ( B) hätte, wie es tatsächlich ist. Dies O(SUM(B) FOR ALL A)kann so umgeschrieben werden O(N), Nals würde die Anzahl der Elemente aller Array-Eingaben definiert.
Meiamsome
4

Python 2.7, 38 Zeichen

F=lambda x,y:{c:1 for c in x+y}.keys()

Sollte O (N) sein und eine gute Hash-Funktion annehmen.

Wasis 8-Zeichen- setImplementierung ist besser, wenn Sie nicht glauben, dass sie gegen die Regeln verstößt.

Keith Randall
quelle
Nett! Verständnis in Python kann so elegant und mächtig sein.
OI
3

PHP, 69/42 68/41 Zeichen

Einschließlich der Funktionsdeklaration sind dies 68 Zeichen:

function m($a,$b){return array_keys(array_flip($a)+array_flip($b));}

Ohne die Funktionsdeklaration sind es 41 Zeichen:

array_keys(array_flip($a)+array_flip($b))
Zamnüsse
quelle
3

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.

merged_arr = {}.tap { |hash| (arr1 + arr2).each { |el| hash[el] ||= el } }.keys

Im Wesentlichen sind dies die Schritte, die ich in der obigen Zeile durchlaufe.

  1. Definieren Sie eine Variable merged_arr, die das Ergebnis enthält
  2. Initialisieren Sie einen leeren, unbenannten Hash als Vermittler, um eindeutige Elemente einzufügen
  3. Verwenden Sie Object#tapdiese Option, um den Hash (auf den hashim tapBlock verwiesen wird ) zu füllen und für die nachfolgende Methodenverkettung zurückzugeben
  4. Verketten arr1und arr2in ein einzelnes, unverarbeitetes Array
  5. Geben Sie für jedes Element elim verketteten Array den Wert elein, hash[el]wenn hash[el]derzeit kein Wert von vorhanden ist. Das Merken hier ( hash[el] ||= el) sichert die Eindeutigkeit der Elemente.
  6. Rufen Sie die Schlüssel (oder Werte, da diese identisch sind) für den jetzt ausgefüllten Hash ab

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:

merged_arr = {}.tap { |hash| (arr1 + arr2).each { |el| hash[el] = 1 } }.keys

Ich liebe es wirklich Object#tap, aber wir können das gleiche Ergebnis erzielen mit Enumerable#reduce:

merged_arr = (arr1 + arr2).reduce({}) { |arr, val| arr[val] = 1; arr }.keys

Sie könnten sogar verwenden Enumberable#map:

merged_arr = Hash[(arr1 + arr2).map { |val| [val, 1] }].keys

Wie ich es in der Praxis machen würde

Abgesehen davon würde ich, wenn ich gebeten würde, zwei Arrays zusammenzuführen arr1und arr2das Ergebnis merged_arreindeutige 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:

merged_arr = arr1 | arr2

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.

OI
quelle
"Verwenden Sie die Array-Funktionen der Standardbibliothek nicht zum Erkennen von Eindeutigkeiten (obwohl andere Elemente der Standardbibliothek in Ordnung sind)"
John Dvorak
Wie verletze ich diese Regel im zweiten Beispiel? Das Auswendiglernen wird an einem Hash durchgeführt. Ist das auch nicht erlaubt?
OI
2
Array.prototype.unique = function()
{
  var o = {},i = this.length
  while(i--)o[this[i]]=true
  return Object.keys(o)
}

Eine Funktion, die n Arrays benötigt, könnte die folgende sein:

function m()
{
  var o={},a=arguments,c=a.length,i;
  while(c--){i=a[c].length;while(i--)o[a[c][i]] = true} 
  return Object.keys(o);
}

Golf, ich denke, das sollte funktionieren (117 Zeichen)

function m(){var o={},a=arguments,c=a.length,i;while(c--){i=a[c].length;while(i--)o[a[c][i]]=1}return Object.keys(o)}

Aktualisieren Wenn Sie den Originaltyp beibehalten möchten, können Sie dies tun

function m()
{
  var o={},a=arguments,c=a.length,f=[],g=[];
  while(c--)g.concat(a[c])
  c = g.length      
  while(c--){if(!o[g[c]]){o[g[c]]=1;f.push(g[c])}}
  return f
}

oder golfen 149:

function m(){var o={},a=arguments,c=a.length,f=[],g=[];while(c--)g.concat(a[c]);c= g.length;while(c--){if(!o[g[c]]){o[g[c]]=1;f.push(g[c])}}return f}

Dies kann immer noch einige Zweifel aufkommen lassen, wenn Sie unterscheiden möchten 123und '123', dann würde dies nicht funktionieren.

Konijn
quelle
Danke für die Antwort. Es ist beeindruckend kurz, aber das macht nur die Hälfte des Problems. Sie müssen auch das eigentliche Zusammenführungsteil (auch wenn es das gleiche ist wie im ursprünglichen Beispiel) in die Lösung einbeziehen und alles in einer Funktion zusammenfassen. Könnten Sie außerdem eine "Golf" -Version anbieten (so wie sie ist O(N))?
HKK
Dadurch werden alle Mitglieder in Strings umgewandelt. zB 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"]
George Reith
2

Python, 46

def A(a,b):print[i for i in b if i not in a]+a

Oder einfach mit der Set-Operation

Python, 8

set(a+b)
War ich
quelle
1
Entschuldigung, es war nicht klar, die Verwendung von Set-Operationen ist auch Betrug.
HKK
Ihr 1. Code enthält Duplikate, wenn sich in a Duplikate befinden oder wenn sich in b Duplikate befinden und sich dieses Element nicht in a befindet.
Vedant Kandoi
2

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 myaus 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)).

use 5.010;
sub unique{
    my%a=map{$_,1}@_;keys%a
}
my @a1 = (1, 2, 3, 4);
my @a2 = (3, 4, 5, 6);
say join " ", unique @a1, @a2;

Ausgabe (zeigt auch Zufälligkeit):

/tmp $ perl unique.pl 
2 3 4 6 1 5
/tmp $ perl unique.pl 
5 4 6 2 1 3
Konrad Borowski
quelle
2

Fortran: 282 252 233 213

Golf Version:

function f(a,b,m,n) result(d);integer::m,n,a(m),b(n),c(m+n);integer,allocatable::d(:);j=m+1;c(1:m)=a(1:m);do i=1,n;if(.not.any(b(i)==c(1:m)))then;c(j)=b(i);j=j+1;endif;enddo;allocate(d(j-1));d=c(1:j-1);endfunction

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:

function f(a,b,m,n) result(d)
  integer::m,n,a(m),b(n),c(m+n)
  integer,allocatable::d(:)
  j=m+1;c(1:m)=a(1:m)
  do i=1,n
     if(.not.any(b(i)==c(1:m)))then
        c(j)=b(i);j=j+1
     endif
  enddo
  allocate(d(j-1))
  d=c(1:j-1)
end function

Dies sollte sein , O(n)wie ich kopiere ain cund dann jeden überprüfen bgegen alle c. Der letzte Schritt ist, den Müll zu beseitigen, der centhalten sein wird, da er nicht initialisiert ist.

Kyle Kanos
quelle
2

Mathematica 10 Zeichen

Union[a,b]

Beispiel:

a={1,2,3,4,5};
b={1,2,3,4,5,6};
Union[a,b]

{1, 2, 3, 4, 5, 6}

Mathematica2 43 Zeichen

Sort@Join[a, b] //. {a___, b_, b_, c___} :> {a, b, c}
Murta
quelle
8
Ich denke, dies würde in die Kategorie der Verwendung von Standard-Library-Array-Methoden gehören.
HKK
Hi @ cloudcoder2000. Es ist nicht erforderlich, eine bestimmte Bibliothek aufzurufen, um Union in Mathematica zu verwenden.
Murta
5
Meiner Meinung nach ist es Betrug, eine eingebaute Funktion zu verwenden, um genau das zu tun, was die Frage verlangt.
Konrad Borowski
ok ok .. der zweite code verwendet keine union.
Murta
1
Ich denke, das Tally[Join[a, b]][[;; , 1]]wäre auch Betrug ;-) Übrigens könnten Sie Zeichen sparen, indem Sie Variablen mit einem Buchstaben verwenden.
Yves Klett
1

Javascript 86

Golf Version:

function m(a,b){var h={};return a.concat(b).filter(function(v){return h[v]?0:h[v]=1})}

Lesbare Version:

function merge(a, b) {
  var hash = {};
  return a.concat(b).filter(function (val) {
    return hash[val] ? 0 : hash[val] = 1;
  });
}
Bertrand
quelle
1
Dies ignoriert falsche Werte ... gibt m([1,0,0,0,0],[0,1,0])zurück [1].
George Reith
1
Wechseln Sie h[v]=vzu h[v]=1.
George Reith
Gut gesehen @GeorgeReith! Wir gingen von 86 auf 84 :)
Bertrand
Es ist immer noch 86, ich glaube, Sie waren verwirrt, weil Sie 2 Zeichen aus der lesbaren Version entfernt haben, nicht das Golfspiel.
George Reith
1

JavaScript 60

Ich benutze ES6 Generator.
Das Folgende kann mit Googles Traceur REPL getestet werden .

m=(i,j)=>{h={};return[for(x of i.concat(j))if(!h[x])h[x]=x]}
Florent
quelle
0

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

var s = new Set(a);      // Complexity O(a.length)
b.forEach(function(e) {  // Complexity O(b.length) * O(s.add())
  s.add(e);
}); 

Probieren Sie es online!


Wenn das obige Snippet verwendet a = [1,2,3]und b = [1,2,3,4,5,6]dann s=[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)wo f(O)die Komplexität ist s.add(O).

Magische Kraken-Urne
quelle
0

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)

Adam
quelle
-2

JavaScript, 131 Zeichen

var array1 = ["Vijendra","Singh"];   
var array2 = ["Singh", "Shakya"];     
result = Array.from(new Set([...array1, ...array2]))
deepak_pal
quelle
4
Willkommen bei PPCG! Bitte teilen Sie uns mit, um welche Sprache es sich handelt, und formatieren Sie sie zur besseren Lesbarkeit als Code. (Dies funktioniert durch Einrücken der Codezeilen mit vier Leerzeichen). Auch eine Erklärung Ihres Ansatzes wäre willkommen.
Laikoni
Es ist nur ein Javascript-Code.
Deepak_pal
@techdeepak Sie können Ihrem Post solche wichtigen Informationen hinzufügen, sie richtig formatieren, Syntaxhervorhebungen hinzufügen und ein bisschen mehr über die Komplexität Ihres Algorithmus schreiben, da dies der schnellste Algorithmus ist . Wie es aussieht, ist dieser Beitrag von relativ geringer Qualität.
Jonathan Frech
-2

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

Endri
quelle
Aus der Frage: Verwenden Sie die Array-Funktionen der Standardbibliothek nicht zum Erkennen von Eindeutigkeiten oder zum Zusammenführen von Sets / Arrays . Außerdem werden dadurch keine Duplikate aus dem Array entfernt
Jo King,
Ich denke, Sie haben diese wichtige Zeile aus der Frage übersehen: " Verwenden Sie die Array-Funktionen der Standardbibliothek nicht zum Erkennen von Eindeutigkeiten oder zum Zusammenführen von Mengen / Arrays "
Peter Taylor
Ja. Das ist richtig. Vielen Dank, dass ihr darauf hingewiesen habt. Kritik wurde demütig aufgenommen.
Endri
@scherzen. Sie haben absolut Recht mit "Verwenden Sie keine Standardbibliotheken ...". Der Rest ist falsch. Die Duplikate werden entfernt. php.net/manual/en/function.array-merge.php . Ich empfehle Ihnen, die PHP-Dokumentation vollständig zu lesen. Ich bin mir zu 100% sicher, dass es den Job macht. Sie müssen nur vorsichtig sein, welches der Arrays Sie als Duplikate betrachten. Prost.
Endri
1
Ich habe den Code in Ihrem Beitrag buchstäblich ohne Änderungen ausgeführt und die Ausgabe enthält Duplikate. Sieht so aus, als sollten Sie die Dokumentation lesen. Wenn die Arrays jedoch numerische Schlüssel enthalten, überschreibt der spätere Wert den ursprünglichen Wert nicht, sondern wird angehängt
Jo King,