Oto, co wymyśliłem, co nie wymaga dodatkowego bitu znaku:
for i := 0 to n - 1
while A[A[i]] != A[i]
swap(A[i], A[A[i]])
end while
end for
for i := 0 to n - 1
if A[i] != i then
print A[i]
end if
end for
Pierwsza pętla permutuje tablicę, więc jeśli element x
występuje przynajmniej raz, to jeden z tych wpisów będzie na pozycji A[x]
.
Zauważ, że może nie wyglądać na O (n) na pierwszy rzut oka, ale tak jest - chociaż ma zagnieżdżoną pętlę, nadal działa w O(N)
czasie. Zamiana występuje tylko wtedy, gdy istnieje i
taka A[i] != i
, a każda zamiana ustawia co najmniej jeden element taki A[i] == i
, że wcześniej nie było to prawdą. Oznacza to, że całkowita liczba swapów (a tym samym całkowita liczba wykonań while
ciała pętli) wynosi co najwyżej N-1
.
Druga pętla wypisuje wartości x
for, które A[x]
nie są równe x
- ponieważ pierwsza pętla gwarantuje, że jeśli x
istnieje co najmniej raz w tablicy, jedno z tych wystąpień będzie w miejscu A[x]
, oznacza to, że drukuje te wartości, x
których nie ma w tablica.
(Link Ideone, abyś mógł się nim bawić)
a[a[i]]
, a ograniczenie spacji O (1) wskazuje naswap()
kluczową operację.5
nie należy do zakresu0..N-1
(N
w tym przypadku jest5
).print
instrukcji naprint i
zmienia ją w rozwiązanie na stackoverflow.com/questions/5249985/ ... i (zakładając, że "torba" jest modyfikowalną tablicą) Qk of stackoverflow.com/questions/3492302/ ...Znakomita odpowiedź caf wypisuje każdą liczbę, która pojawia się k razy w tablicy k-1 razy. To przydatne zachowanie, ale pytanie prawdopodobnie wymaga, aby każdy duplikat był drukowany tylko raz, a on nawiązuje do możliwości zrobienia tego bez przekraczania granic czasu liniowego / stałej przestrzeni. Można to zrobić, zastępując jego drugą pętlę następującym pseudokodem:
Wykorzystuje to właściwość, która
m
polega na tym, że po uruchomieniu pierwszej pętli, jeśli jakakolwiek wartość pojawi się więcej niż raz, to jeden z tych wyglądów będzie miał właściwą pozycję, a mianowicieA[m]
. Jeśli będziemy ostrożni, możemy użyć tej „domowej” lokalizacji do przechowywania informacji o tym, czy jakiekolwiek duplikaty zostały jeszcze wydrukowane, czy nie.W wersji caf, gdy przeszliśmy przez tablicę,
A[i] != i
sugerowaliśmy, żeA[i]
jest to duplikat. W mojej wersji opieram się na nieco innym niezmienniku:A[i] != i && A[A[i]] == A[i]
oznaczaA[i]
to, że jest to duplikat , którego wcześniej nie widzieliśmy . (Jeśli pominiesz część „której nie widzieliśmy wcześniej”, resztę można uznać za wynikającą z prawdy niezmiennika kawiarni i gwarancji, że wszystkie duplikaty mają jakąś kopię w lokalizacji domowej). początek (po zakończeniu pierwszej pętli kawiarni) i pokazuję poniżej, że jest utrzymywany po każdym kroku.Gdy przechodzimy przez tablicę, sukces
A[i] != i
części testu sugeruje, żeA[i]
może to być duplikat, którego wcześniej nie widziano. Jeśli wcześniej tego nie widzieliśmy, spodziewamy sięA[i]
, że lokalizacja domu wskazuje na siebie - to jest sprawdzane pod kątem drugiej połowyif
warunku. W takim przypadku drukujemy go i zmieniamy lokalizację początkową, aby wskazywała z powrotem na ten pierwszy znaleziony duplikat, tworząc dwuetapowy „cykl”.Aby zobaczyć, że ta operacja nie zmienia naszego niezmiennika, załóżmy, że
m = A[i]
określona pozycja jesti
satysfakcjonującaA[i] != i && A[A[i]] == A[i]
. To oczywiste, że zmiana robimy (A[A[i]] = i
) będzie działać, aby zapobiec inne wystąpienia non-domum
od bycia wyjście jako duplikaty powodując 2. połowę swoichif
warunkach zawodzą, ale to będzie działać, gdyi
przybywa do lokalizacji domowejm
? Tak, będzie, ponieważ teraz, chociażi
teraz okazuje się, że pierwsza połowaif
warunkuA[i] != i
jest prawdziwa, druga połowa sprawdza, czy lokalizacja, na którą wskazuje, jest lokalizacją domową i stwierdza, że tak nie jest. W tej sytuacji już nie wiem czym
czyA[m]
był duplikatem wartość, ale wiemy, że tak czy inaczej,zostało to już zgłoszone , ponieważ gwarantuje się, że te 2 cykle nie pojawią się w wyniku pierwszej pętli kawiarni. (Zauważ, że jeślim != A[m]
wtedy dokładnie jeden zm
iA[m]
występuje więcej niż raz, a drugi nie występuje w ogóle).źródło
Oto pseudokod
Przykładowy kod w C ++
źródło
-
z~
o zerowej emisji.O(n)
ukrytą przestrzeń -n
bity znaku. Jeśli tablica jest zdefiniowana w taki sposób, że każdy element może przechowywać tylko wartości między0
an-1
, to oczywiście nie działa.Dla stosunkowo małego N możemy użyć operacji div / mod
Nie C / C ++, ale w każdym razie
http://ideone.com/GRZPI
źródło
Niezbyt ładne, ale przynajmniej łatwo jest zobaczyć właściwości O (N) i O (1). Zasadniczo skanujemy tablicę i dla każdej liczby sprawdzamy, czy odpowiadająca jej pozycja została oznaczona jako już widziana-raz (N), czy już-widziana-wiele razy (N + 1). Jeśli jest oznaczony jako już widziany raz, drukujemy go i wielokrotnie oznaczamy jako już widziany. Jeśli nie jest oflagowany, oznaczamy go już raz widzianym i przenosimy oryginalną wartość odpowiedniego indeksu do bieżącej pozycji (oznaczanie jest operacją destrukcyjną).
lub jeszcze lepiej (szybciej, pomimo podwójnej pętli):
źródło
if (value > i) a[i--] = a[value];
działa: jeślivalue <= i
więc przetworzyliśmy już wartość wa[value]
i możemy ją bezpiecznie nadpisać. Nie powiedziałbym też, że natura O (N) jest oczywista! Literowanie: czas wykonania głównej pętliN
plus ile razya[i--] = a[value];
przebiega linia. Ta linia może być uruchamiana tylko wtedya[value] < N
, gdy i za każdym razem, gdy jest uruchamiana, zaraz potem wartość tablicy, która nie została jeszczeN
ustawionaN
, jest więc uruchamiana w większościN
przypadków, w sumie co najwyżej2N
iteracji pętli.Jedno rozwiązanie w C to:
Jest to złożoność przestrzeni O (n) i O (1).
źródło
Załóżmy, że prezentujemy tę tablicę jako jednokierunkową strukturę danych grafu - każda liczba jest wierzchołkiem, a jej indeks w tablicy wskazuje na inny wierzchołek tworzący krawędź wykresu.
Dla jeszcze większej prostoty mamy indeksy od 0 do n-1 i zakres liczb od 0..n-1. na przykład
0 (3) -> 3 (3) to cykl.
Odpowiedź: Wystarczy przejść przez tablicę opartą na indeksach. jeśli a [x] = a [y], to jest to cykl, a zatem duplikat. Przejdź do następnego indeksu i kontynuuj jeszcze raz i tak dalej, aż do końca tablicy. Złożoność: O (n) czas i O (1) przestrzeń.
źródło
Mały kod w Pythonie pokazujący metodę caf powyżej:
źródło
i
wartości - zwróć uwagę nawhile
moją odpowiedź.Algorytm można łatwo zobaczyć w poniższej funkcji C. Odzyskanie oryginalnej tablicy, chociaż nie jest wymagane, będzie możliwe z każdym wpisem modulo n .
Ideone Link do testowania.
źródło
źródło
Stworzyłem jedną przykładową aplikację na plac zabaw w bardzo krótkim czasie, aby znaleźć duplikaty w czasie 0 (n) złożoności i stałej dodatkowej przestrzeni. Sprawdź adres URL Znajdowanie duplikatów
Rozwiązanie IMP Above działało, gdy tablica zawiera elementy od 0 do n-1, a każda z tych liczb pojawia się dowolną liczbę razy.
źródło
źródło
Jeśli tablica nie jest zbyt duża, to rozwiązanie jest prostsze, tworzy kolejną tablicę o tym samym rozmiarze do zaznaczania.
1 Utwórz bitmapę / tablicę o takim samym rozmiarze jak tablica wejściowa
2 zeskanuj swoją tablicę wejściową i zwiększ jej liczbę w powyższej tablicy
3 Teraz zeskanuj tablicę check_list i wydrukuj duplikat raz lub tyle razy, ile zostały powielone
Oczywiście zajmuje to dwa razy więcej miejsca niż rozwiązanie podane powyżej, ale efektywność czasowa wynosi O (2n), czyli w zasadzie O (n).
źródło
O(1)
przestrzeń.