Znajdź „dziurę” na liście liczb

Jaki jest najszybszy sposób na znalezienie pierwszej (najmniejszej) liczby całkowitej, która nie istnieje na danej liście nieposortowanych liczb całkowitych (i która jest większa niż najmniejsza wartość na liście)?

Moje prymitywne podejście polega na ich sortowaniu i przeglądaniu listy, czy jest lepszy sposób?

Zakładając, że masz na myśli „liczbę całkowitą”, kiedy mówisz „liczba”, możesz użyć bitvectora o rozmiarze 2 ^ n, gdzie n jest liczbą elementów (powiedzmy, że twój zakres obejmuje liczby całkowite od 1 do 256, wtedy możesz użyć 256- bit lub 32 bajt, bitvector). Gdy natrafisz na liczbę całkowitą w pozycji n swojego zakresu, ustaw n-ty bit.

Kiedy skończysz wyliczanie zbioru liczb całkowitych, iterujesz po bitach w swoim bitvektorze, szukając pozycji dowolnego zestawu bitów 0. Teraz pasują one do pozycji n brakujących liczb całkowitych.

Jest to O (2 * N), dlatego O (N) i prawdopodobnie bardziej wydajna pamięć niż sortowanie całej listy.

Jeśli najpierw posortujesz całą listę, gwarantujesz najgorszy czas działania. Ponadto wybór algorytmu sortowania ma kluczowe znaczenie.

Oto jak podejdę do tego problemu:

1. Użyj sortowania sterty , koncentrując się na najmniejszych elementach na liście.
2. Po każdej zamianie sprawdź, czy masz lukę.
3. Jeśli znajdziesz lukę, to return: Znalazłeś swoją odpowiedź.
4. Jeśli nie znajdziesz przerwy, kontynuuj zamianę.

Oto wizualizacja rodzaju sterty .

Aby być ezoterycznym i „sprytnym”, w specjalnym przypadku tablicy mającej tylko jedną „dziurę” możesz wypróbować rozwiązanie oparte na XOR:

• Określ zasięg swojej tablicy; odbywa się to poprzez ustawienie zmiennej „max” i „min” na pierwszy element tablicy, a następnie dla każdego elementu, jeśli ten element jest mniejszy niż min lub większy niż maksimum, ustaw min lub maks na Nowa wartość.
• Jeśli zasięg jest o jeden mniejszy niż liczność zbioru, jest tylko jeden „otwór”, więc możesz użyć XOR.
• Zainicjuj zmienną całkowitą X na zero.
• Dla każdej liczby całkowitej od min. Do maks. Włącznie, XOR tę wartość z X i zapisz wynik w X.
• Teraz XOR każdą liczbę całkowitą w tablicy z X, przechowując każdy kolejny wynik do X jak poprzednio.
• Kiedy skończysz, X ​​będzie wartością twojej „dziury”.

To będzie działać w przybliżeniu 2N czas podobny do rozwiązania bitvector, ale wymaga mniej miejsca w pamięci dla dowolnego N> sizeof (int). Jeśli jednak tablica ma wiele „otworów”, X będzie „sumą” wszystkich otworów, która będzie trudna lub niemożliwa do rozdzielenia na rzeczywiste wartości otworów. W takim przypadku powracasz do innej metody, takiej jak podejście „przestawne” lub „bitvector” z innych odpowiedzi.

Można to również powtórzyć, używając czegoś podobnego do metody przestawnej, aby jeszcze bardziej zmniejszyć złożoność. Zmień kolejność tablic w oparciu o punkt obrotu (który będzie maksimum lewej strony i min prawej strony; ustalenie maksimum i min pełnej tablicy podczas obracania będzie trywialne). Jeśli lewa strona czopa ma jeden lub więcej otworów, cofnij się tylko na tę stronę; w przeciwnym razie wróć na drugą stronę. W dowolnym momencie, w którym możesz ustalić, że jest tylko jeden otwór, użyj metody XOR, aby go znaleźć (co powinno być ogólnie tańsze niż kontynuowanie obracania się aż do zbioru dwóch elementów ze znanym otworem, który jest podstawowym przypadkiem algorytm czystego obrotu).

Jaki zakres liczb napotkasz? Jeśli ten zakres nie jest bardzo duży, możesz rozwiązać ten problem za pomocą dwóch skanów (czas liniowy O (n)), używając tablicy z tyloma elementami, ile masz liczb, wymieniając przestrzeń na czas. Możesz znaleźć zakres dynamicznie za pomocą jednego skanu. Aby zmniejszyć ilość miejsca, możesz przypisać 1 bit do każdej liczby, co daje 8 wartości pamięci na bajt.

Inną opcją, która może być lepsza we wczesnych scenariuszach i byłaby insitu zamiast kopiowania pamięci, jest zmodyfikowanie sortowania wyboru, aby wyjść wcześniej, jeśli min znaleziony w przebiegu skanowania nie jest o 1 większy niż ostatnia znaleziona min.

Nie, nie bardzo. Ponieważ jakikolwiek jeszcze nie skanowany numer zawsze może być tym, który wypełnia daną „dziurę”, nie można uniknąć skanowania każdego numeru przynajmniej raz, a następnie porównywania go z możliwymi sąsiadami. Prawdopodobnie możesz przyspieszyć, budując drzewo binarne lub tak dalej, a następnie przesuwając je od lewej do prawej, aż do znalezienia dziury, ale jest to zasadniczo taka sama złożoność czasowa jak sortowanie, ponieważ sortuje. I prawdopodobnie nie wymyślisz niczego szybciej niż Timsort .

Większość pomysłów to nie tylko sortowanie. Wersja bitvector to zwykły Bucketsort. Wspomniano także o rodzaju sterty. Zasadniczo sprowadza się do wyboru właściwego algorytmu sortowania, który zależy od wymagań czasowych / przestrzennych, a także od zasięgu i liczby elementów.

Moim zdaniem użycie struktury sterty jest prawdopodobnie najbardziej ogólnym rozwiązaniem (sterty zasadniczo zapewniają najmniejsze elementy skutecznie bez pełnego sortowania).

Możesz również przeanalizować podejścia, które najpierw znajdują najmniejsze liczby, a następnie skanują każdą liczbę całkowitą większą niż ta. Lub znajdziesz 5 najmniejszych liczb, mając nadzieję, że będą miały lukę.

Wszystkie te algorytmy mają swoją siłę w zależności od charakterystyki wejściowej i wymagań programu.

Rozwiązanie, które nie wykorzystuje dodatkowej pamięci lub nie przyjmuje szerokości (32 bitów) liczb całkowitych.

1. W jednym przejściu liniowym znajdź najmniejszą liczbę. Nazwijmy to „min”. O (n) złożoność czasu.

2. Wybierz losowy element przestawny i wykonaj partycję w stylu Quicksort.

3. Jeśli element przestawny zakończył się w pozycji = („pivot” - „min”), to powtórz po prawej stronie partycji, w przeciwnym razie powtórz po lewej stronie partycji. Chodzi o to, że jeśli od początku nie ma żadnych otworów, oś obrotu znajdowałaby się w („pivot” - „min”) pozycji, więc pierwszy otwór powinien leżeć po prawej stronie przegrody i odwrotnie.

4. Walizka podstawowa to tablica 1 elementu, a otwór znajduje się między tym elementem a następnym.

Oczekiwana złożoność całkowitego czasu pracy wynosi O (n) (8 * n ze stałymi), a najgorszym przypadkiem jest O (n ^ 2). Analiza złożoności czasowej dla podobnego problemu można znaleźć tutaj .

Wydaje mi się, że wpadłem na coś, co powinno działać ogólnie i wydajnie, jeśli masz gwarancję, że nie będziesz mieć duplikatów * (jednak powinno być rozszerzalne na dowolną liczbę dziur i dowolny zakres liczb całkowitych).

Pomysł tej metody jest podobny do szybkiego sortowania, polegającego na tym, że wokół niej znajduje się czop i przegroda, a następnie nawiercane po bokach z otworem. Aby zobaczyć, które strony mają otwór, znajdujemy najniższą i najwyższą liczbę i porównujemy je z osią obrotu i liczbą wartości po tej stronie. Załóżmy, że oś obrotu to 17, a minimalna liczba to 11. Jeśli nie ma otworów, powinno być 6 liczb (11, 12, 13, 14, 15, 16, 17). Jeśli jest ich 5, wiemy, że po tej stronie jest dziura i możemy po tej stronie wrócić, aby ją znaleźć. Mam problem z wyjaśnieniem tego bardziej precyzyjnie, więc weźmy przykład.

15 21 10 13 18 16 22 23 24 20 17 11 25 12 14

Sworzeń:

10 13 11 12 14 |15| 21 18 16 22 23 24 20 17 25

15 jest osią obrotu oznaczoną potokami ( ||). Po lewej stronie osi obrotu znajduje się 5 cyfr, takich jak powinno być (15–10), i 9 po prawej stronie, gdzie powinno być 10 (25–15). Tak więc powracamy po prawej stronie; zauważymy, że poprzednia granica wynosiła 15 w przypadku, gdy otwór przylega do niej (16).

[15] 18 16 17 20 |21| 22 23 24 25

Teraz po lewej stronie są 4 liczby, ale powinno być 5 (21–16). Wracamy więc tam i ponownie zanotujemy poprzednią granicę (w nawiasach).

[15] 16 17 |18| 20 [21]

Lewa strona ma poprawne 2 liczby (18–16), ale prawa ma 1 zamiast 2 (20–18). W zależności od naszych warunków końcowych moglibyśmy porównać liczbę 1 z dwiema stronami (18, 20) i zobaczyć, czy brakuje 19 lub powtórzyć jeszcze raz:

[18] |20| [21]

Lewa strona ma rozmiar zero, z odstępem między czopem (20) a poprzednim obrzeżem (18), więc 19 to otwór.

*: Jeśli są duplikaty, prawdopodobnie możesz użyć zestawu skrótów, aby usunąć je w czasie O (N), zachowując ogólną metodę O (N), ale może to zająć więcej czasu niż użycie innej metody.