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ą.
[1, 2, 2, 3]
i[2, 3, 4]
zwrócić,[1, 2, 2, 3, 4]
czy[1, 2, 3, 4]
?Odpowiedzi:
Perl
27 znaków
Prosty hack Perla
Jestem pewien, że ktoś mógłby to zrobić w jednej linii… i tym samym (Dzięki Dom Hastings)
źródło
sub x{$_{$_}++for@_;keys%_}
(w przypadku sprowadzenia do remisu) i użyć go jako:z((1,2,3,4),(2,3,4,5,6))
JavaScript O (N)
13112411692 (86?)Wersja golfowa:
Wersja golfowa czytelna dla człowieka:
Mógłbym tak użyć
concat
i zrobić to w 86 znakach: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):
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.
źródło
O(N)
.O(A*B)
(nie używanie,N
ponieważ jest mylące). Byłoby tak, gdyby każda tablica wejściowa (każdaA
) miała taką samą liczbę elementów (B
), jaka jest w rzeczywistościO(SUM(B) FOR ALL A)
, co można przepisać tak, jakO(N)
przy definiowaniuN
jako liczba elementów wszystkich danych wejściowych w tablicy.Python 2.7, 38 znaków
Powinno być O (N) przy założeniu dobrej funkcji skrótu.
set
Implementacja 8 postaci Wasi jest lepsza, jeśli nie uważasz, że narusza to zasady.źródło
PHP,
69/4268/41 znakówŁącznie z deklaracją funkcji jest 68 znaków:
Bez uwzględnienia deklaracji funkcji ma 41 znaków:
źródło
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.
Zasadniczo są to kroki, które przechodzę w powyższej linii.
merged_arr
która będzie zawierać wynikObject#tap
do zapełniania skrótu (oznaczonego jakhash
wtap
bloku) i zwraca go do późniejszego tworzenia łańcuchów metodarr1
iarr2
w jednym szeregu, nieprzetworzonejel
w łączonej tablicy umieścić wartośćel
whash[el]
jeśli ma wartośćhash[el]
obecnie istnieje. Memoization here (hash[el] ||= el
) zapewnia unikalność elementów.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:
Naprawdę kocham
Object#tap
, ale możemy osiągnąć ten sam wynik, używającEnumerable#reduce
:Możesz nawet użyć
Enumberable#map
:Jak zrobiłbym to w praktyce
Powiedziawszy to wszystko, jeśli zadano scalić dwie tablice
arr1
iarr2
takie, że wynikmerged_arr
ma 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: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.źródło
Funkcja, która pobierałaby n tablic, mogłaby wyglądać następująco:
Gra w golfa, myślę, że powinno to działać (117 znaków)
Aktualizacja Jeśli chcesz zachować oryginalny typ, możesz
lub grał w golfa 149:
To jeszcze może rzucić pewne wątpliwości, jeśli chcesz się wyróżnić
123
i'123'
, to nie będzie działać ..źródło
O(N)
?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"]
python, 46
Lub używając po prostu operacji ustawiania
python, 8
źródło
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
my
z 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)).Dane wyjściowe (również pokazujące losowość):
źródło
Fortran:
282252233213Wersja golfowa:
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ą:
To powinno być
O(n)
jak skopiowaća
doc
, a następnie sprawdzić każdyb
przeciwko wszystkimc
. Ostatnim krokiem jest wyeliminowanie śmieci, którec
będą zawierać, ponieważ są niezainicjowane.źródło
Mathematica 10 znaków
Przykład:
Mathematica2 43 znaki
źródło
Tally[Join[a, b]][[;; , 1]]
oszukuje również ;-) BTW, możesz zapisać znaki przy użyciu zmiennych jednoliterowych.JavaScript 86
Wersja golfowa:
Wersja do odczytu:
źródło
m([1,0,0,0,0],[0,1,0])
powraca[1]
.h[v]=v
nah[v]=1
.JavaScript 60
Używam generatora ES6.
Poniższe można przetestować przy użyciu Google Traceur REPL .
źródło
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
Wypróbuj online!
Jeśli powyższy fragment używa
a = [1,2,3]
ib = [1,2,3,4,5,6]
następnies=[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 jestn + n * f(O)
tam, gdzief(O)
jest złożonośćs.add(O)
.źródł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)
źródło
JavaScript, 131 znaków
źródło
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);
źródło