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ą.

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%_}

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

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.

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

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.

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ć ..

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)

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

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.

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}

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

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

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

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)

JavaScript, 131 znaków

var array1 = ["Vijendra","Singh"];   
var array2 = ["Singh", "Shakya"];     
result = Array.from(new Set([...array1, ...array2]))

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