Scal tablicę bez duplikatów

15

Ostatnio widziałem ten kod JavaScript na StackOverflow do łączenia dwóch tablic i usuwania duplikatów:

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

Chociaż ten kod działa, jest okropnie nieefektywny ( O(n^2)). Twoim wyzwaniem jest stworzenie algorytmu o mniejszej złożoności.

Kryteria wygranej to rozwiązanie o najmniejszej złożoności , ale więzi zostaną zerwane przez najkrótszą długość znaków.

Wymagania :

Spakuj cały kod razem w funkcję spełniającą następujące wymagania dotyczące „poprawności”:

  • Wejście: dwie tablice
  • Wyjście: jedna tablica
  • Scala elementy obu tablic razem - Każdy element w obu tablicach wejściowych musi znajdować się w tablicy wyjściowej.
  • Tablica wyjściowa nie powinna mieć duplikatów.
  • Kolejność nie ma znaczenia (w przeciwieństwie do oryginału)
  • Dowolny język się liczy
  • Nie używaj funkcji tablicy standardowej biblioteki do wykrywania unikatowości lub łączenia zestawów / tablic (chociaż inne rzeczy ze standardowej biblioteki są w porządku). Pozwólcie mi rozróżnić, że konkatenacja tablic jest w porządku, ale funkcje, które już wykonują wszystkie powyższe czynności, nie są.
hkk
źródło
Jak mamy stworzyć lub dołączyć do tablicy bez korzystania z funkcji tablicy?
Emil Vikström
@ EmilVikström Zobacz moją edycję. Miałem na myśli, że nie można używać funkcji unikatowości tablic. Przepraszam, że jestem niejasny.
hkk
Jeśli jedna z tablic ma w sobie duplikaty, to czy je również usuwamy? Na przykład, czy należy połączyć [1, 2, 2, 3]i [2, 3, 4]zwrócić, [1, 2, 2, 3, 4]czy [1, 2, 3, 4]?
OI
1
@OI Tak, to by było zbyt łatwe.
hkk
1
Czy mogę zapytać: tablice czego ? Czy możemy założyć po prostu liczby całkowite lub łańcuchy, czy też musimy dopuścić bardziej złożone rzeczy, takie jak obiekty wielopoziomowe?
jawns317

Odpowiedzi:

8

Perl

27 znaków

Prosty hack Perla

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

Jestem pewien, że ktoś mógłby to zrobić w jednej linii… i tym samym (Dzięki Dom Hastings)

sub x{$_{$_}++for@_;keys%_}
Zach Leighton
źródło
1
„Nie używaj funkcji tablicy standardowej biblioteki do wykrywania unikatowości (chociaż inne rzeczy z biblioteki standardowej są w porządku)”
John Dvorak
1
Jak naruszam tę zasadę? Nie używam unikalnych funkcji?
Zach Leighton
Jak to działa? Przepraszam, nie mogę odczytać perla. Jeśli odczytuje klucze mapy skrótów - czy to się liczy w przypadku tej reguły? Nie będę głosować, dopóki się nie przekonam.
John Dvorak
1
Łączy tablice, zapętla obie i dodaje do skrótu zwiększającego wartość, której kluczem jest bieżąca wartość w pętli tablicowej. Potem bierze klucze tego skrótu, użyłem tego w niektórych moich pracach. Więc [1,1,2,3,4,4] staje się {1 => 2, 2 => 1, 3 => 1 , 4 => 2}
Zach Leighton
@ZachLeighton możesz skrócić kod do 27 znaków za pomocą sub x{$_{$_}++for@_;keys%_}(w przypadku sprowadzenia do remisu) i użyć go jako:z((1,2,3,4),(2,3,4,5,6))
Dom Hastings
10

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

Wersja golfowa:

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}

Wersja golfowa czytelna dla człowieka:

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
}

Mógłbym tak użyć concati zrobić to w 86 znakach:

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

Ale nie jestem pewien, czy nadal jest to O (N) oparte na tym JsPerf: http://jsperf.com/unique-array-merging-concat-vs-looping, ponieważ wersja concat jest nieznacznie szybsza z mniejszymi tablicami, ale wolniejsza z większe tablice (Chrome 31 OSX).

W praktyce rób to (golf jest pełen złych praktyk):

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

Nie jestem dobry w złożoności obliczeniowej, ale wierzę, że tak jest O(N). Chciałbym, gdyby ktoś mógł to wyjaśnić.

Edycja: Oto wersja, która pobiera dowolną liczbę tablic i łączy je.

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
źródło
To jest prawie dokładnie to, co zamierzałem opublikować w ciągu kilku sekund :-( Tak, to jest amortyzowany czas liniowy, jeśli tabele skrótów są implementowane z amortyzowanym stałym czasem wstawiania i wyszukiwania (co jest powszechne w wielu językach, nie wiem konkretnie o JS)
Emil Vikström
@ EmilVikström Dzięki za to, jak sądzę, JavaScript ma, ale nie mam na to dowodów. Przepraszam za szybkie palce, spowolniłem komentarzami: P
George Reith
To świetne podejście. Czy jednak oprócz ładnie sformatowanej wersji mógłbyś również zaoferować rozwiązanie w stylu „golfowego kodu”? Widząc, że wiele osób uważało to za właściwe podejście, prawdopodobnie będzie to miało związek O(N).
hkk
@ cloudcoder2000 Ok, chciałem wydrukować pełną wersję, ponieważ wersja z kodem golfowym prawdopodobnie będzie mniej wydajna w praktyce.
George Reith,
1
@ cloudcoder2000 Nie są w pełni niezależne, więc najgorszy przypadek to nie O(A*B)(nie używanie, Nponieważ jest mylące). Byłoby tak, gdyby każda tablica wejściowa (każda A) miała taką samą liczbę elementów ( B), jaka jest w rzeczywistości O(SUM(B) FOR ALL A), co można przepisać tak, jak O(N)przy definiowaniu Njako liczba elementów wszystkich danych wejściowych w tablicy.
meiamsome
4

Python 2.7, 38 znaków

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

Powinno być O (N) przy założeniu dobrej funkcji skrótu.

setImplementacja 8 postaci Wasi jest lepsza, jeśli nie uważasz, że narusza to zasady.

Keith Randall
źródło
Ładny! Rozumienie w Pythonie może być tak eleganckie i potężne.
OI
3

PHP, 69/42 68/41 znaków

Łącznie z deklaracją funkcji jest 68 znaków:

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

Bez uwzględnienia deklaracji funkcji ma 41 znaków:

array_keys(array_flip($a)+array_flip($b))
zamnuts
źródło
3

Jeden sposób w Ruby

Aby zachować zgodność z zasadami opisanymi powyżej, użyłbym podobnej strategii jak rozwiązanie JavaScript i użyłem skrótu jako pośrednika.

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

Zasadniczo są to kroki, które przechodzę w powyższej linii.

  1. Zdefiniuj zmienną, merged_arrktóra będzie zawierać wynik
  2. Zainicjuj pusty, nienazwany skrót jako pośrednik, aby wstawić unikalne elementy
  3. Służy Object#tapdo zapełniania skrótu (oznaczonego jak hashw tapbloku) i zwraca go do późniejszego tworzenia łańcuchów metod
  4. Łączy arr1i arr2w jednym szeregu, nieprzetworzonej
  5. Dla każdego elementu elw łączonej tablicy umieścić wartość elw hash[el]jeśli ma wartość hash[el]obecnie istnieje. Memoization here ( hash[el] ||= el) zapewnia unikalność elementów.
  6. Pobierz klucze (lub wartości, ponieważ są takie same) dla obecnie zapełnionego skrótu

To powinno się uruchomić O(n) czasie. Daj mi znać, jeśli wydałem jakieś niedokładne stwierdzenia lub jeśli mogę poprawić powyższą odpowiedź pod względem wydajności lub czytelności.

Możliwe ulepszenia

Korzystanie z zapamiętywania jest prawdopodobnie niepotrzebne, biorąc pod uwagę, że klucze do skrótu będą unikalne, a wartości nie mają znaczenia, więc jest to wystarczające:

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

Naprawdę kocham Object#tap, ale możemy osiągnąć ten sam wynik, używając Enumerable#reduce:

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

Możesz nawet użyć Enumberable#map:

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

Jak zrobiłbym to w praktyce

Powiedziawszy to wszystko, jeśli zadano scalić dwie tablice arr1i arr2takie, że wynik merged_arrma unikalne elementy i może wykorzystać dowolną metodę Ruby do mojej dyspozycji, chciałbym po prostu użyć operatora zestaw Związku, który jest przeznaczony do rozwiązywania dokładnie ten problem:

merged_arr = arr1 | arr2

Szybkie spojrzenie na źródło Array#|wydaje się jednak potwierdzać, że użycie skrótu jako pośrednika wydaje się być akceptowalnym rozwiązaniem do przeprowadzenia unikatowego scalenia między 2 tablicami.

OI
źródło
„Nie używaj funkcji tablicy standardowej biblioteki do wykrywania unikatowości (chociaż inne rzeczy z biblioteki standardowej są w porządku)”
John Dvorak
Jak naruszam tę zasadę w drugim przykładzie? Zapamiętywanie jest wykonywane na haszu. Czy to też nie jest dozwolone?
OI
2
Array.prototype.unique = function()
{
  var o = {},i = this.length
  while(i--)o[this[i]]=true
  return Object.keys(o)
}

Funkcja, która pobierałaby n tablic, mogłaby wyglądać następująco:

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

Gra w golfa, myślę, że powinno to działać (117 znaków)

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

Aktualizacja Jeśli chcesz zachować oryginalny typ, możesz

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
}

lub grał w golfa 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}

To jeszcze może rzucić pewne wątpliwości, jeśli chcesz się wyróżnić 123i '123', to nie będzie działać ..

Konijn
źródło
Dziękuję za odpowiedź. Jest imponująco krótki, ale to tylko połowa problemu. Musisz również dołączyć do rozwiązania rzeczywistą łączącą się część (nawet jeśli jest taka sama jak w oryginalnym przykładzie) i połączyć wszystko razem w jedną funkcję. Czy oprócz tego (w obecnej formie) możesz podać wersję „golfową” O(N)?
hkk
To powoduje, że wszyscy członkowie są w ciągi. np. m([1,2,3,4,5],[2,3,4,5,6],[2,3,4,5,6,7])staje się["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

Lub używając po prostu operacji ustawiania

python, 8

set(a+b)
Czy byłem
źródło
1
Niestety, nie było jasne, używanie operacji ustawiania jest również oszustwem.
hkk
Twój pierwszy kod będzie miał duplikaty, jeśli są duplikaty w a lub jeśli są duplikaty wb, a ten element nie jest w a.
Vedant Kandoi
2

Perl

23 bajty, jeśli liczymy tylko blok kodu wewnątrz podprogramu. Może być 21, jeśli dozwolone jest zastępowanie wartości globalnych (spowoduje to usunięcie myz kodu). Zwraca elementy w losowej kolejności, ponieważ kolejność nie ma znaczenia. Jeśli chodzi o złożoność, średnio jest to O (N) (zależy od liczby kolizji skrótu, ale są one raczej rzadkie - w najgorszym przypadku może to być O (N 2 ) (ale nie powinno się to zdarzyć, ponieważ Perl może wykryć patologiczne skróty) , i zmienia ziarno funkcji skrótu, gdy wykryje takie zachowanie)).

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;

Dane wyjściowe (również pokazujące losowość):

/tmp $ perl unique.pl 
2 3 4 6 1 5
/tmp $ perl unique.pl 
5 4 6 2 1 3
Konrad Borowski
źródło
2

Fortran: 282 252 233 213

Wersja golfowa:

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

Które nie tylko wygląda nieskończenie lepiej, ale faktycznie skompiluje się (zbyt długa linia w formie golfa) z czytelną dla człowieka formą:

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

To powinno być O(n)jak skopiować ado c, a następnie sprawdzić każdy bprzeciwko wszystkim c. Ostatnim krokiem jest wyeliminowanie śmieci, które cbędą zawierać, ponieważ są niezainicjowane.

Kyle Kanos
źródło
2

Mathematica 10 znaków

Union[a,b]

Przykład:

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

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

Mathematica2 43 znaki

Sort@Join[a, b] //. {a___, b_, b_, c___} :> {a, b, c}
Murta
źródło
8
Myślę, że należałoby to do kategorii standardowych metod tablic bibliotecznych.
hkk
Cześć @ cloudcoder2000. Nie trzeba dzwonić do konkretnej biblioteki, aby korzystać z Union w Mathematica.
Murta
5
Moim zdaniem używanie wbudowanej funkcji do robienia dokładnie tego, o co pyta to oszustwo.
Konrad Borowski
ok ok .. drugi kod nie używa Unii.
Murta
1
Sądzę, że Tally[Join[a, b]][[;; , 1]]oszukuje również ;-) BTW, możesz zapisać znaki przy użyciu zmiennych jednoliterowych.
Yves Klett
1

JavaScript 86

Wersja golfowa:

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

Wersja do odczytu:

function merge(a, b) {
  var hash = {};
  return a.concat(b).filter(function (val) {
    return hash[val] ? 0 : hash[val] = 1;
  });
}
Bertrand
źródło
1
To ignoruje wartości falsey ... m([1,0,0,0,0],[0,1,0])powraca [1].
George Reith
1
Zmień h[v]=vna h[v]=1.
George Reith
Dobrze zauważony @GeorgeReith! Poszliśmy z 86 do 84 :)
Bertrand
Nadal jest 86, myślę, że się pomyliłeś, ponieważ usunąłeś 2 postacie z czytelnej wersji, a nie z golfa.
George Reith,
1

JavaScript 60

Używam generatora ES6.
Poniższe można przetestować przy użyciu Google Traceur REPL .

m=(i,j)=>{h={};return[for(x of i.concat(j))if(!h[x])h[x]=x]}
Florent
źródło
0

Jeśli szukasz implementacji opartej na JavaScript, która by była wydajna, opiera się na obiektach leżących u podstaw obiektu, po prostu użyłbym Seta. Zwykle w implementacji obiekt Set z natury obsługuje unikalne obiekty podczas wstawiania z pewnego rodzaju indeksowaniem wyszukiwania binarnego. Wiem, że w Javie jest to log(n)wyszukiwanie za pomocą wyszukiwania binarnego, ponieważ żaden zestaw nie może zawierać jednego obiektu więcej niż jeden raz.


Chociaż nie mam pojęcia, czy dotyczy to również Javascript, do n*log(n)implementacji może wystarczyć coś tak prostego, jak następujący fragment kodu :

JavaScript , 61 bajtów

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

Wypróbuj online!


Jeśli powyższy fragment używa a = [1,2,3]ib = [1,2,3,4,5,6] następnie s=[1,2,3,4,5,6].

Jeśli znasz złożoność Set.add(Object)funkcji w JavaScript, daj mi znać, złożoność tego jest n + n * f(O)tam, gdzie f(O)jest złożoność s.add(O).

Urna Magicznej Ośmiornicy
źródło
0

APL (Dyalog Unicode) , O (N), 28 bajtów

Anonimowa funkcja ukrytej poprawki.

(⊢(/⍨)⍳∘≢=⍳⍨),

Wypróbuj online!

, połącz argumenty; NA)

() Zastosuj do tego następującą anonimową funkcję ukrytą; O (1)

   ⍳⍨ indeksy selfie (wskaźniki pierwszego wystąpienia każdego elementu w całej tablicy); NA)

  = porównaj element po elemencie z; NA):

   ⍳∘≢ wskaźniki długości tablicy; NA)

(/⍨) użyj tego do filtrowania; NA):

   niezmodyfikowany argument; O (1)

O (N + 1 + N + N + N + N + 1) = O (N)

Adám
źródło
-2

JavaScript, 131 znaków

var array1 = ["Vijendra","Singh"];   
var array2 = ["Singh", "Shakya"];     
result = Array.from(new Set([...array1, ...array2]))
deepak_pal
źródło
4
Witamy w PPCG! Poinformuj nas, który to język, i sformatuj go jako kod, aby uzyskać lepszą czytelność. (Działa to poprzez wcięcie linii kodu czterema spacjami). Docenione zostanie również wyjaśnienie twojego podejścia.
Laikoni
to tylko kod javascript.
deepak_pal
@techdeepak Możesz dodać tak ważne informacje do swojego postu, odpowiednio sformatować je, dodać podświetlanie składni i napisać nieco więcej o złożoności algorytmu, ponieważ jest to najszybszy algorytm . W tej chwili ten post jest dość niskiej jakości.
Jonathan Frech
-2

PHP około 28 znaków [pomijając przykładowe zmienne tablicowe i zmienne wynikowe].

$ tablica1 = tablica (1, 2, 3); $ tablica2 = tablica (3, 4, 5);

$ result = array_merge ($ array1, $ array2);

Endri
źródło
Z pytania: nie używaj standardowych funkcji tablicowych biblioteki do wykrywania unikatowości lub łączenia zestawów / tablic . Co więcej, to tak naprawdę nie usuwa duplikatów z tablicy
Jo King
Myślę, że przeoczyłeś tę ważną linię z pytania: „ Nie używaj standardowych funkcji tablicowych biblioteki do wykrywania unikatowości lub łączenia zestawów / tablic
Peter Taylor,
Tak. To jest poprawne. Dziękuję wam za wskazanie tego. Krytyka przyjęta z pokorą.
Endri,
@jo king. Masz całkowitą rację co do „Nie używaj standardowych bibliotek ...”. Reszta jest błędna. Usuwa duplikaty. php.net/manual/en/function.array-merge.php . Polecam w pełni przeczytać dokumentację PHP. Jestem w 100% pewien, że to zadziała. Trzeba tylko uważać, która z tablic uważa się za duplikaty. Twoje zdrowie.
Endri,
1
Dosłownie uruchomiłem kod w twoim zgłoszeniu bez zmian, a dane wyjściowe mają duplikaty. Wygląda na to, że powinieneś przeczytać dokumentację, a mianowicie jeśli jednak tablice zawierają klucze numeryczne, późniejsza wartość nie zastąpi pierwotnej wartości, ale zostanie dołączona
Jo King