Minimalna niepowtarzalny numer w tablicy jest zdefiniowana jako min{v|v occurs only once in the array} Na przykład, minimalna niepowtarzalnym numerem {1, 4, 1, 2, 3} jest 2. jest jakiś lepiej niż sortowanie?znalezienie minimalnej niepowtarzalny numer w tablicy
Wierzę, że to jest O (N) rozwiązanie zarówno w czasie i przestrzeni:
HashSet seenOnce; // sufficiently large that access is O(1)
HashSet seenMultiple; // sufficiently large that access is O(1)
for each in input // O(N)
if item in seenMultiple
next
if item in seenOnce
remove item from seenOnce
add to item seenMultiple
else
add to item seeOnce
smallest = SENTINEL
for each in seenOnce // worst case, O(N)
if item < smallest
smallest = item
Jeśli masz ograniczony zakres wartości integralnych można wymienić HashSets z BitArrays zaindeksowane przez wartości.
To wszystko świetnie, proszę pana, ale gdzie mogę znaleźć tę magiczną funkcję skrótu dostępu losowego O (1), o której mówisz? O ile ja (i reszta świata) wiem, że "najlepszym" czasem dostępu losowego dla funkcji mieszania jest O (logn). – ElKamina
O ile czegoś nie brakuje, nie jest wymagany dostęp losowy. Pierwszy przebieg przechodzi przez 'input' (O (N)) i wykonuje wyszukiwanie, wstawienia i usunięcia na zestawach skrótów, każdy O (1). Razem: O (N). Drugie przejście, jak napisane obecnie pętle nad 'seenOnce', ale to łatwo naprawić: po prostu zapętlić ponownie' input' (O (N)), przetestować członkostwo w 'seenOnce' (O (1)), a jeśli jest tam dopisać do nowej 'seenOnceList' (O (1)), całkowitej O (N). Na koniec wykonaj skanowanie dla minimum, O (N). Net O (N), nie? – DSM
@ElKamina - Mylicie drzewo z hash. Zobacz http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions i spójrz na listę pod O (1). Przy dużym stole i odpowiedniej funkcji skrótu kolizje są nieznaczne. – walrii
Nie musisz wykonywać pełnego sortowania. Wykonuj wewnętrzną pętlę sortowania bąbelkowego, aż uzyskasz wyraźną minimalną wartość na jednym końcu. W najlepszym wypadku będzie to mieć złożoność czasową O (k * n), gdzie k = liczba nierozróżnialnych wartości minimalnych. Jednak najgorszym przypadku złożoność jest O (n * n). Tak więc może to być efektywne, gdy oczekiwana wartość k < < n.
Myślę, że byłaby to minimalna możliwa złożoność czasu, chyba że można dostosować dowolne algorytmy sortowania O (n * logn) do powyższego zadania.
"Lepsze", co oznacza "mniejszą złożoność czasu"? –
@VaughnCato: tak, zastanawiam się, czy możemy zrobić lepiej niż O (nlogn). – shilk
Czy zakres Twoich wartości jest ograniczony lub ograniczony? Jeśli są one integralne z ograniczonym zakresem, uważam, że O (N) jest możliwy. – walrii