Łatwe pytanie do wywiadu stało się trudniejsze: biorąc pod uwagę liczby 1..100, znajdź brakujące liczby, których dokładnie brakuje


1146

Niedawno miałem ciekawe doświadczenie w rozmowie kwalifikacyjnej. Pytanie zaczęło się naprawdę łatwo:

Q1 : Mamy torbę zawierającą numery 1, 2, 3, ..., 100. Każda liczba pojawia się dokładnie raz, więc jest 100 liczb. Teraz jedna liczba jest losowo wybierana z torby. Znajdź brakujący numer.

Oczywiście wcześniej słyszałem to pytanie, więc bardzo szybko odpowiedziałem w następujący sposób:

A1 : Cóż, suma liczb 1 + 2 + 3 + … + Nto (N+1)(N/2)(patrz Wikipedia: suma szeregów arytmetycznych ). Bo N = 100suma to 5050.

Tak więc, jeśli wszystkie liczby są obecne w torbie, suma będzie dokładnie 5050. Ponieważ brakuje jednej liczby, suma będzie mniejsza niż ta, a różnicą jest ta liczba. Możemy więc znaleźć tę brakującą liczbę w O(N)czasie i O(1)przestrzeni.

W tym momencie myślałem, że dobrze mi poszło, ale nagle pytanie przybrało nieoczekiwany obrót:

Q2 : Zgadza się, ale teraz jak byś to zrobił, gdyby DWIE liczby brakowały?

Nigdy wcześniej nie widziałem / nie słyszałem / nie rozważałem tej odmiany, więc spanikowałem i nie mogłem odpowiedzieć na pytanie. Ankieter nalegał na zapoznanie się z moim procesem myślowym, więc wspomniałem, że być może możemy uzyskać więcej informacji, porównując z oczekiwanym produktem, lub może wykonując drugie przejście po zebraniu informacji z pierwszego przejścia itp., Ale tak naprawdę to po prostu strzelałem w ciemności, zamiast mieć właściwie ścieżkę do rozwiązania.

Ankieter próbował mnie zachęcić, mówiąc, że posiadanie drugiego równania jest rzeczywiście jednym ze sposobów rozwiązania problemu. W tym momencie byłem trochę zdenerwowany (za to, że nie znałem wcześniej odpowiedzi) i zapytałem, czy to jest ogólna (czytaj: „przydatna”) technika programowania, czy może to tylko odpowiedź na podstęp / gotcha.

Zaskoczyła mnie odpowiedź ankietera: możesz uogólnić technikę, by znaleźć 3 brakujące liczby. W rzeczywistości możesz go uogólnić, aby znaleźć k brakujących liczb.

Pytanie : Jeśli dokładnie brakuje liczby k z torby, jak byś ją skutecznie znalazł?

To było kilka miesięcy temu i nadal nie mogłem zrozumieć, co to za technika. Oczywiście nie jest to Ω(N)czas dolna granica ponieważ musimy skanować wszystkie numery co najmniej raz, ale wywiad podkreślał, że CZAS i PRZESTRZEŃ złożoność techniki rozwiązywania (minus O(N)skanowania wejściowego czasu) jest zdefiniowana w k nie N .

Pytanie jest proste:

  • Jak rozwiązałbyś Q2 ?
  • Jak rozwiązałbyś Q3 ?
  • Jak rozwiązałbyś Qk ?

Wyjaśnienia

  • Generalnie jest N liczb od 1 .. N , nie tylko 1..100.
  • Nie szukam oczywistego rozwiązania opartego na zestawie, np. Używając zestawu bitów , kodując obecność / nieobecność każdej liczby wartością wyznaczonego bitu, a zatem używając O(N)bitów w dodatkowej przestrzeni. Nie możemy sobie pozwolić na dodatkową przestrzeń proporcjonalna do N .
  • Nie szukam też oczywistego podejścia do sortowania. To i podejście oparte na zestawie warto wspomnieć w wywiadzie (są łatwe do wdrożenia, aw zależności od N mogą być bardzo praktyczne). Szukam rozwiązania Świętego Graala (które może, ale nie musi być praktyczne do wdrożenia, ale mimo to ma pożądane cechy asymptotyczne).

Więc znowu, oczywiście, musisz zeskanować dane wejściowe O(N), ale możesz przechwycić tylko niewielką ilość informacji (zdefiniowaną w kategoriach k nie N ), a następnie jakoś znaleźć k brakujących liczb.


7
@polygenelubricants Dziękujemy za wyjaśnienia. „Szukam algorytmu, który wykorzystuje czas O (N) i przestrzeń O (K), gdzie K jest liczbą nieobecnych liczb” byłoby jasne od samego początku ;-)
Dave O.

7
Powinieneś sprecyzować w zestawieniu Q1, że nie możesz uzyskać dostępu do liczb w kolejności. Prawdopodobnie wydaje ci się to oczywiste, ale nigdy nie słyszałem o tym pytaniu, a termin „torba” (co oznacza również „multiset”) był nieco mylący.
Jérémie,

7
Przeczytaj poniższe odpowiedzi, ponieważ podane tutaj odpowiedzi są absurdalne: stackoverflow.com/questions/4406110/…

18
Rozwiązanie sumowania liczb wymaga miejsca na log (N), chyba że uznasz, że miejsce na nieograniczoną liczbę całkowitą to O (1). Ale jeśli zezwalasz na nieograniczone liczby całkowite, masz tyle miejsca, ile chcesz za pomocą tylko jednej liczby całkowitej.
Udo Klein

3
Nawiasem mówiąc, całkiem fajnym alternatywnym rozwiązaniem dla Q1 może być obliczenie XORwszystkich liczb od 1do n, a następnie xoring wynik ze wszystkimi liczbami w podanej tablicy. W końcu brakuje ci numeru. W tym rozwiązaniu nie musisz przejmować się przepełnieniem, jak w podsumowaniu.
sbeliakov

Odpowiedzi:


590

Oto podsumowanie linku Dimitrisa Andreou .

Pamiętaj sumę i-tych mocy, gdzie i = 1,2, .., k. Zmniejsza to problem do rozwiązania układu równań

a 1 + a 2 + ... + a k = b 1

a 1 2 + a 2 2 + ... + a k 2 = b 2

...

a 1 k + a 2 k + ... + a k k = b k

Korzystanie tożsamości Newtona , wiedząc, b i pozwala obliczyć

c 1 = a 1 + a 2 + ... a k

c 2 = a 1 a 2 + a 1 a 3 + ... + a k-1 a k

...

c k = a 1 a 2 ... a k

Jeśli rozszerzysz wielomian (xa 1 ) ... (xa k ), współczynniki będą wynosić dokładnie c 1 , ..., c k - patrz wzory Viète . Ponieważ każdy czynnik wielomianu jest jednoznacznie (pierścień wielomianów jest domeną euklidesową ), oznacza to, że i są jednoznacznie określone, aż do permutacji.

To kończy dowód na to, że zapamiętywanie mocy wystarcza do odzyskania liczb. Dla stałego k jest to dobre podejście.

Jednak gdy k jest zmienne, bezpośrednie podejście do obliczania c 1 , ..., c k jest zbyt drogie, ponieważ np. C k jest iloczynem wszystkich brakujących liczb, wielkości n! / (Nk) !. Aby temu zaradzić, wykonaj obliczenia w polu Z q , gdzie q jest liczbą pierwszą taką, że n <= q <2n - istnieje zgodnie z postulatem Bertranda . Dowodu nie trzeba zmieniać, ponieważ formuły wciąż się utrzymują, a rozkład na czynniki wielomianowe jest nadal wyjątkowy. Potrzebujesz również algorytmu faktoryzacji nad polami skończonymi, na przykład algorytmu Berlekamp lub Cantor-Zassenhaus .

Pseudokod wysokiego poziomu dla stałej k:

  • Oblicz i -te potęgi podanych liczb
  • Odejmij, aby uzyskać sumy i-tych potęg nieznanych liczb. Nazwij sumy b i .
  • Tożsamości Skorzystaj Newtona dla współczynników obliczeniowych z b I ; nazywaj je c i . Zasadniczo, c 1 = b 1 ; c 2 = (c 1 b 1 - b 2 ) / 2; dokładne formuły można znaleźć w Wikipedii
  • Uwzględnij wielomian x k -c 1 x k-1 + ... + c k .
  • Korzenie wielomianu to potrzebne liczby a 1 , ..., k .

Aby zmienić k, znajdź liczbę pierwszą n <= q <2n za pomocą np. Millera-Rabina i wykonaj kroki ze wszystkimi liczbami zmniejszonymi modulo q.

EDYCJA: Poprzednia wersja tej odpowiedzi stwierdzała, że ​​zamiast Z q , gdzie q jest liczbą pierwszą, możliwe jest użycie pola skończonego o charakterystyce 2 (q = 2 ^ (log n)). Tak nie jest, ponieważ formuły Newtona wymagają dzielenia przez liczby do k.


6
Nie musisz używać pola głównego, możesz także użyć q = 2^(log n). (Jak udało ci się zrobić super- i indeksy dolne ?!)
Heinrich Apfelmus

49
+1 To jest naprawdę, bardzo sprytne. Jednocześnie wątpliwe jest, czy naprawdę warto podjąć wysiłek, czy też (części) rozwiązanie dość sztucznego problemu można ponownie wykorzystać w inny sposób. I nawet jeśli byłby to rzeczywisty problem na wielu platformach, najbardziej trywialne O(N^2)rozwiązanie prawdopodobnie przewyższy to piękno nawet na dość wysokim poziomie N. Sprawia, że ​​myślę o tym: tinyurl.com/c8fwgw Niemniej jednak świetna robota! Nie miałbym cierpliwości, by czołgać się przez całą matematykę :)
back2dos

167
Myślę, że to wspaniała odpowiedź. Myślę, że to również pokazuje, jak kiepskie byłoby pytanie z wywiadu, aby rozszerzyć brakujące liczby poza jeden. Nawet pierwszy z nich to rodzaj gotchya, ale jest na tyle powszechny, że w zasadzie pokazuje, że „przygotowałeś wywiad”. Ale oczekiwanie, że major CS wie, że wykracza poza k = 1 (szczególnie „na miejscu” w wywiadzie) jest trochę głupie.
corsiKa

5
To skutecznie robi kodowanie Reeda Solomona na wejściu.
David Ehrmann

78
Założę się, że wpisanie całej liczby hash setai iteracja po 1...Npakiecie za pomocą odnośników w celu ustalenia, czy brakuje numerów, byłoby najbardziej ogólne, najszybsze średnio pod względem kodmian, najbardziej debugowalne, najbardziej łatwe do utrzymania i zrozumiałe rozwiązanie. Oczywiście sposób matematyczny jest imponujący, ale gdzieś po drodze musisz być inżynierem, a nie matematykiem. Zwłaszcza, gdy w grę wchodzi biznes.
v.oddou

243

Znajdziesz go, czytając kilka stron Muthukrishnan - Algorytmy strumienia danych: Puzzle 1: Znajdowanie brakujących liczb . Pokazuje dokładnie uogólnienie, którego szukasz . Prawdopodobnie to właśnie przeczytał twój ankieter i dlaczego zadał te pytania.

Teraz, gdyby tylko ludzie zaczęli usuwać odpowiedzi, które zostały zastąpione lub zastąpione przez leczenie Muthukrishnana, i ułatwiłyby znalezienie tego tekstu. :)


Zobacz także bezpośrednio spokrewnioną odpowiedź sdcvvc , która zawiera również pseudokod (hurra! Nie trzeba czytać tych skomplikowanych formuł matematycznych :)) (dzięki, świetna robota!).


Oooh ... To interesujące. Muszę przyznać, że matematyka trochę mnie zdezorientowała, ale ja to przeszukiwałem. Może zostawić to otwarte, aby móc przyjrzeć się później. :) I +1, aby ten link był łatwiejszy do znalezienia. ;-)
Chris

2
Link do książek Google nie działa dla mnie. Oto lepsza wersja [plik PostScript].
Heinrich Apfelmus

9
Łał. Nie spodziewałem się, że zostanie to ocenione pozytywnie! Ostatnim razem, gdy zamieściłem odniesienie do rozwiązania (w tym przypadku Knutha), zamiast próbować go rozwiązać samodzielnie, faktycznie zostało to zanegowane: stackoverflow.com/questions/3060104/ ... Bibliotekarz we mnie się cieszy, dziękuję :)
Dimitris Andreou

@Apfelmus, pamiętaj, że jest to wersja robocza. (Nie obwiniam cię oczywiście, myliłem szkic prawdziwych rzeczy przez prawie rok, zanim znalazłem książkę). Btw, jeśli link nie zadziałał, możesz przejść na books.google.com i wyszukać „algorytmy strumienia danych Muthukrishnan” (bez cudzysłowów), pojawia się pierwszy.
Dimitris Andreou

2
Przeczytaj poniższe odpowiedzi, ponieważ podane tutaj odpowiedzi są absurdalne: stackoverflow.com/questions/4406110/…

174

Możemy rozwiązać Q2, sumując zarówno same liczby, jak i kwadraty liczb.

Możemy wtedy zredukować problem do

k1 + k2 = x
k1^2 + k2^2 = y

Gdzie xi yjak daleko sumy są poniżej oczekiwanych wartości.

Zastąpienie daje nam:

(x-k2)^2 + k2^2 = y

Które możemy następnie rozwiązać, aby określić nasze brakujące liczby.


7
+1; Wypróbowałem formułę w Maple dla wybranych liczb i działa. Nadal nie mogłem się przekonać, DLACZEGO to działa.
polygenelubricants

4
@polygenelubricants: Jeśli chciał udowodnić prawidłowość, byś najpierw pokazać, że zawsze zapewnia się prawidłowe rozwiązanie (to znaczy, że zawsze wytwarza parę liczb, które po wyjęciu z zestawu, by doprowadzić do pozostałej części zestawu konieczności zaobserwowana suma i suma kwadratów). Stamtąd udowodnienie wyjątkowości jest tak proste, jak wykazanie, że produkuje tylko jedną taką parę liczb.
Anon.

5
Charakter równań oznacza, że ​​z tego równania otrzymasz dwie wartości k2. Jednak z pierwszego równania używanego do wygenerowania k1 można zauważyć, że te dwie wartości k2 będą oznaczać, że k1 jest drugą wartością, więc masz dwa rozwiązania, które są tymi samymi liczbami w odwrotny sposób. Gdybyście podstępnie zadeklarowali, że k1> k2, mieliby tylko jedno rozwiązanie równania kwadratowego, a zatem jedno rozwiązanie ogółem. I wyraźnie z natury pytania zawsze istnieje odpowiedź, więc zawsze działa.
Chris

3
Dla danej sumy k1 + k2 istnieje wiele par. Możemy zapisać te pary jako K1 = a + b i K2 = ab gdzie a = (K1 + k2 / 2). a jest unikalny dla danej sumy. Suma kwadratów (a + b) ** 2 + (ab) ** 2 = 2 * (a 2 + b 2). Dla danej sumy K1 + K2, składnik 2 jest stały i widzimy, że suma kwadratów będzie unikalna z powodu składnika b 2. Dlatego wartości xiy są unikalne dla pary liczb całkowitych.
phkahler

8
To jest niesamowite. @ user3281743 oto przykład. Niech brakujące liczby (k1 i k2) będą wynosić 4 i 6. Suma (1 -> 10) = 55 i Suma (1 ^ 2 -> 10 ^ 2) = 385. Teraz niech x = 55 - (Suma (Wszystkie pozostałe liczby )) y = 385 - (Suma (kwadraty wszystkich pozostałych liczb)), więc x = 10 i y = 52. Zamień jak pokazano, co pozostawia nam: (10 - k2) ^ 2 + k2 ^ 2 = 52, które możesz uprość do: 2k ^ 2 - 20k + 48 = 0. Rozwiązanie równania kwadratowego daje 4 i 6 jako odpowiedź.
AlexKoren,

137

Jak zauważył @j_random_hacker, jest to dość podobne do znajdowania duplikatów w czasie O (n) i przestrzeni O (1) , tutaj też działa adaptacja mojej odpowiedzi.

Zakładając, że „torba” jest reprezentowana przez tablicę A[]wielkości opartą na 1 N - k, możemy rozwiązać Qk w O(N)czasie i O(k)dodatkowej przestrzeni.

Po pierwsze, rozszerzamy naszą tablicę A[]o kelementy, aby była teraz wielkości N. To jest O(k)dodatkowa przestrzeń. Następnie uruchamiamy następujący algorytm pseudokodowy:

for i := n - k + 1 to n
    A[i] := A[1]
end for

for i := 1 to n - k
    while A[A[i]] != A[i] 
        swap(A[i], A[A[i]])
    end while
end for

for i := 1 to n
    if A[i] != i then 
        print i
    end if
end for

Pierwsza pętla inicjuje kdodatkowe wpisy do tego samego, co pierwszy wpis w tablicy (jest to po prostu wygodna wartość, o której wiemy, że jest już w tablicy - po tym kroku wszelkie wpisy, których brakowało w początkowej tablicy rozmiaru, N-ksą wciąż brakuje w rozszerzonej tablicy).

Druga pętla permutuje rozszerzoną tablicę, więc jeśli element xjest obecny co najmniej raz, to jeden z tych wpisów będzie na pozycji A[x].

Zauważ, że chociaż ma zagnieżdżoną pętlę, nadal działa w O(N)czasie - zamiana występuje tylko wtedy, gdy istnieje itaka A[i] != i, a każda zamiana ustawia co najmniej jeden element taki A[i] == i, w którym wcześniej nie było to prawdą. Oznacza to, że łączna liczba zamian (a tym samym łączna liczba wykonań whileciała pętli) wynosi co najwyżej N-1.

Trzecia pętla wypisuje te indeksy tablicy i, które nie są zajęte przez wartość i- oznacza to, że imusiała jej brakować.


4
Zastanawiam się, dlaczego tak niewiele osób głosuje na tę odpowiedź, a nawet nie oznaczyło jej jako poprawnej. Oto kod w Pythonie. Działa w czasie O (n) i potrzebuje dodatkowej przestrzeni O (k). pastebin.com/9jZqnTzV
wall-e

3
@caf jest to dość podobne do ustawiania bitów i liczenia miejsc, w których bit ma wartość 0. I myślę, że podczas tworzenia tablicy liczb całkowitych zajętych jest więcej pamięci.
Fox

5
„Ustawienie bitów i zliczanie miejsc, w których bit ma wartość 0”, wymaga dodatkowej spacji O (n), to rozwiązanie pokazuje, jak wykorzystać dodatkową spację O (k).
caf

7
Nie działa ze strumieniami jako danymi wejściowymi i modyfikuje tablicę wejściową (chociaż bardzo mi się podoba i pomysł jest owocny).
comco

3
@ v.oddou: Nie, w porządku. Zamiana ulegnie zmianie A[i], co oznacza, że ​​następna iteracja nie będzie porównywać tych samych dwóch wartości, co poprzednia. Nowa A[i]będzie taka sama jak w ostatniej pętli A[A[i]], ale nowa A[A[i]]będzie nową wartością. Wypróbuj i przekonaj się.
caf

128

Poprosiłem czterolatka o rozwiązanie tego problemu. Sortował liczby, a potem liczył dalej. Wymaga miejsca O (podłoga kuchenna) i działa równie łatwo, jakkolwiek brakuje wielu kulek.


20
;) Twój 4-letni musi zbliżać się do 5 lub / i jest geniuszem. moja 4-letnia córka nie może jeszcze poprawnie policzyć do 4. Cóż, szczerze mówiąc, powiedzmy, że ledwo w końcu zintegrowała istnienie „4”. inaczej do tej pory zawsze to pomija. „1,2,3,5,6,7” była jej zwykłą sekwencją liczenia. Poprosiłem ją, aby dodała ołówki, a ona poradziłaby sobie z wynikiem 1 + 2 = 3, licząc wszystko od nowa. Martwię się właściwie ...: '(meh ..
v.oddou

proste, ale skuteczne podejście.
PabTorre

6
O (podłoga kuchenna) haha ​​- ale czy to nie byłby O (n ^ 2)?

13
O (m²) chyba :)
Viktor Mellgren

1
@phuclv: w odpowiedzi stwierdzono, że „ wymaga miejsca O (podłoga kuchenna)”. Ale w każdym razie jest to przypadek, w którym sortowanie można osiągnąć w czasie O (n) --- patrz ta dyskusja .
Anthony Labarre,

36

Nie jestem pewien, czy jest to najbardziej wydajne rozwiązanie, ale zapętlibym wszystkie wpisy i użyję zestawu bitów, aby zapamiętać, które liczby są ustawione, a następnie przetestować pod kątem 0 bitów.

Lubię proste rozwiązania - a nawet wierzę, że może to być szybsze niż obliczenie sumy lub sumy kwadratów itp.


11
Zaproponowałem tę oczywistą odpowiedź, ale nie tego chciał ankieter. W pytaniu wyraźnie powiedziałem, że nie takiej odpowiedzi szukam. Kolejna oczywista odpowiedź: najpierw sortuj. Nie szukam O(N)ani sposobu liczenia, ani sortowania O(N log N)porównawczego, chociaż oba są bardzo prostymi rozwiązaniami.
polygenelubricants

@polygenelubricants: Nie mogę znaleźć, gdzie powiedziałeś to w swoim pytaniu. Jeśli uważasz, że zestaw bitów jest wynikiem, nie ma drugiego przejścia. Złożoność jest (jeśli uważamy, że N jest stała, jak sugeruje ankieter mówiąc, że złożoność jest „zdefiniowana w k nie N”) O (1), a jeśli potrzebujesz skonstruować bardziej „czysty” wynik, uzyskaj O (k), co jest najlepszym, co możesz uzyskać, ponieważ zawsze potrzebujesz O (k), aby uzyskać czysty wynik.
Chris Lercher,

„Zauważ, że nie szukam oczywistego rozwiązania opartego na zestawie (np. Używając zestawu bitów”). Ostatni akapit z pierwotnego pytania.
hrnt

9
@hmt: Tak, pytanie zostało zredagowane kilka minut temu. Podaję tylko odpowiedź, której oczekiwałbym od rozmówcy ... Sztuczne konstruowanie rozwiązania nieoptymalnego (nie możesz pokonać czasu O (n) + O (k), bez względu na to, co robisz) nie robi ma to dla mnie sens - z wyjątkiem sytuacji, gdy nie stać Cię na O (n) dodatkowe miejsce, ale pytanie nie jest jednoznaczne.
Chris Lercher

3
Zredagowałem pytanie ponownie, aby wyjaśnić. Doceniam informację zwrotną / odpowiedź.
polygenelubricants

33

Nie sprawdziłem matematyki, ale podejrzewam, że obliczanie Σ(n^2)w tym samym przebiegu, w którym wykonujemy obliczenia Σ(n), dostarczyłoby wystarczających informacji, aby uzyskać dwie brakujące liczby, Zrób Σ(n^3)również, jeśli są trzy, i tak dalej.


15

Problem z rozwiązaniami opartymi na sumach liczb polega na tym, że nie biorą one pod uwagę kosztów przechowywania i pracy z liczbami z dużymi wykładnikami ... w praktyce, aby działało to dla bardzo dużych liczb n, używana byłaby biblioteka dużych liczb . Możemy analizować wykorzystanie przestrzeni dla tych algorytmów.

Możemy analizować złożoność czasu i przestrzeni algorytmów sdcvvc i Dimitrisa Andreou.

Przechowywanie:

l_j = ceil (log_2 (sum_{i=1}^n i^j))
l_j > log_2 n^j  (assuming n >= 0, k >= 0)
l_j > j log_2 n \in \Omega(j log n)

l_j < log_2 ((sum_{i=1}^n i)^j) + 1
l_j < j log_2 (n) + j log_2 (n + 1) - j log_2 (2) + 1
l_j < j log_2 n + j + c \in O(j log n)`

Więc l_j \in \Theta(j log n)

Wykorzystane miejsce do przechowywania: \sum_{j=1}^k l_j \in \Theta(k^2 log n)

Wykorzystane miejsce: przy założeniu, że obliczenia a^jwymagają ceil(log_2 j)czasu, całkowity czas:

t = k ceil(\sum_i=1^n log_2 (i)) = k ceil(log_2 (\prod_i=1^n (i)))
t > k log_2 (n^n + O(n^(n-1)))
t > k log_2 (n^n) = kn log_2 (n)  \in \Omega(kn log n)
t < k log_2 (\prod_i=1^n i^i) + 1
t < kn log_2 (n) + 1 \in O(kn log n)

Całkowity wykorzystany czas: \Theta(kn log n)

Jeśli ten czas i przestrzeń są wystarczające, możesz użyć prostego algorytmu rekurencyjnego. Niech b! I będzie i-tym wpisem w torbie, n liczbą liczb przed przeprowadzkami, a k liczbą przeprowadzek. W składni Haskell ...

let
  -- O(1)
  isInRange low high v = (v >= low) && (v <= high)
  -- O(n - k)
  countInRange low high = sum $ map (fromEnum . isInRange low high . (!)b) [1..(n-k)]
  findMissing l low high krange
    -- O(1) if there is nothing to find.
    | krange=0 = l
    -- O(1) if there is only one possibility.
    | low=high = low:l
    -- Otherwise total of O(knlog(n)) time
    | otherwise =
       let
         mid = (low + high) `div` 2
         klow = countInRange low mid
         khigh = krange - klow
       in
         findMissing (findMissing low mid klow) (mid + 1) high khigh
in
  findMising 1 (n - k) k

Wykorzystana pamięć: O(k)dla listy, O(log(n))dla stosu: O(k + log(n)) ten algorytm jest bardziej intuicyjny, ma tę samą złożoność czasu i zajmuje mniej miejsca.


1
+1, wygląda ładnie, ale straciłeś mnie przechodząc od linii 4 do linii 5 we fragmencie nr 1 - czy możesz to wyjaśnić dalej? Dzięki!
j_random_hacker

isInRangeto O (log n) , a nie O (1) : porównuje liczby z zakresu 1..n, więc musi porównać bity O (log n) . Nie wiem, w jakim stopniu ten błąd wpływa na resztę analizy.
jcsahnwaldt mówi GoFundMonica

14

Poczekaj minutę. Jak podano pytanie, w torbie znajduje się 100 liczb. Bez względu na to, jak duże jest k, problem można rozwiązać w stałym czasie, ponieważ można użyć zestawu i usunąć liczby z zestawu co najwyżej 100-k iteracji pętli. 100 jest stałe. Zestaw pozostałych liczb jest twoją odpowiedzią.

Jeśli uogólnimy rozwiązanie liczb od 1 do N, nic się nie zmienia, z wyjątkiem tego, że N nie jest stałą, więc mamy czas O (N - k) = O (N). Na przykład, jeśli użyjemy zestawu bitów, ustawiamy bity na 1 w czasie O (N), iterujemy liczby, ustawiając bity na 0 w miarę upływu czasu (O (Nk) = O (N)), a następnie mam odpowiedź.

Wydaje mi się, że ankieter pytał cię, jak wydrukować zawartość końcowego zestawu w czasie O (k) zamiast w czasie O (N). Oczywiście, po ustawieniu nieco bitów, musisz iterować przez wszystkie N bitów, aby ustalić, czy powinieneś wydrukować numer, czy nie. Jeśli jednak zmienisz sposób implementacji zestawu, możesz wydrukować liczby w iteracjach. Odbywa się to poprzez umieszczenie liczb w obiekcie, który ma być przechowywany zarówno w zestawie skrótów, jak i podwójnie połączonej liście. Kiedy usuwasz obiekt z zestawu skrótów, usuwasz go również z listy. Odpowiedzi pozostaną na liście, która ma teraz długość k.


9
Ta odpowiedź jest zbyt prosta i wszyscy wiemy, że proste odpowiedzi nie działają! ;) Poważnie, jednak oryginalne pytanie powinno prawdopodobnie podkreślać wymaganą przestrzeń O (k).
DK.

Problem nie jest prosty, ale musisz użyć dodatkowej pamięci O (n) na mapę. Problem mnie rozwiązał w stałym czasie i stałej pamięci
Mojo Risin

3
Założę się, że możesz udowodnić, że minimalnym rozwiązaniem jest przynajmniej O (N). ponieważ mniej oznaczałoby, że nawet NIE WYGLĄDAŁEŚ na niektóre liczby, a ponieważ nie określono żadnego zamówienia, sprawdzanie WSZYSTKICH liczb jest obowiązkowe.
v.oddou

Jeśli spojrzymy na dane wejściowe jako strumień, a n jest zbyt duże, aby utrzymać go w pamięci, wymóg pamięci O (k) ma sens. Nadal możemy używać haszowania: po prostu twórz wiadra k ^ 2 i używaj prostego algorytmu sumowania na każdym z nich. To tylko pamięć k ^ 2 i można użyć kilku innych segmentów, aby uzyskać wysokie prawdopodobieństwo sukcesu.
Thomas Ahle,

8

Aby rozwiązać pytanie o brakujące liczby 2 (i 3), możesz zmodyfikować quickselect, który średnio działa O(n)i używa stałej pamięci, jeśli partycjonowanie jest wykonywane w miejscu.

  1. Podziel zestaw względem losowego elementu przestawnego pna partycje l, które zawierają liczby mniejsze niż element przestawny i rktóre zawierają liczby większe niż element przestawny.

  2. Określ, w których partycjach znajdują się 2 brakujące liczby, porównując wartość przestawną z rozmiarem każdej partycji ( p - 1 - count(l) = count of missing numbers in li n - count(r) - p = count of missing numbers in r)

  3. a) Jeśli w każdej partycji brakuje jednego numeru, użyj metody różnicy sum, aby znaleźć każdą brakującą liczbę.

    (1 + 2 + ... + (p-1)) - sum(l) = missing #1 i ((p+1) + (p+2) ... + n) - sum(r) = missing #2

    b) Jeśli partycja jest brak zarówno liczby i partycja jest pusty, wówczas brakujące wartości to zarówno (p-1,p-2)lub (p+1,p+2) w zależności od podziału brakuje liczby.

    Jeśli w jednej partycji brakuje 2 liczb, ale nie jest pusta, wróć do tej partycji.

Przy tylko 2 brakujących liczbach ten algorytm zawsze odrzuca co najmniej jedną partycję, więc zachowuje O(n)średni czas złożoności szybkiego wyboru. Podobnie, przy 3 brakujących liczbach, algorytm ten odrzuca również co najmniej jedną partycję z każdym przejściem (ponieważ jak w przypadku 2 brakujących liczb, co najwyżej tylko 1 partycja będzie zawierać wiele brakujących liczb). Nie jestem jednak pewien, o ile wydajność spada, gdy dodaje się więcej brakujących liczb.

Oto implementacja, która nie korzysta z partycjonowania w miejscu, więc ten przykład nie spełnia wymagań dotyczących miejsca, ale ilustruje kroki algorytmu:

<?php

  $list = range(1,100);
  unset($list[3]);
  unset($list[31]);

  findMissing($list,1,100);

  function findMissing($list, $min, $max) {
    if(empty($list)) {
      print_r(range($min, $max));
      return;
    }

    $l = $r = [];
    $pivot = array_pop($list);

    foreach($list as $number) {
      if($number < $pivot) {
        $l[] = $number;
      }
      else {
        $r[] = $number;
      }
    }

    if(count($l) == $pivot - $min - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($min, $pivot-1)) - array_sum($l) . "\n";
    }
    else if(count($l) < $pivot - $min) {
      // more than 1 missing number, recurse
      findMissing($l, $min, $pivot-1);
    }

    if(count($r) == $max - $pivot - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($pivot + 1, $max)) - array_sum($r) . "\n";
    } else if(count($r) < $max - $pivot) {
      // mroe than 1 missing number recurse
      findMissing($r, $pivot+1, $max);
    }
  }

Próbny


Partycjonowanie zestawu przypomina używanie przestrzeni liniowej. Przynajmniej nie działałoby w ustawieniach przesyłania strumieniowego.
Thomas Ahle,

@ThomasAhle patrz en.wikipedia.org/wiki/Selection_alameterm#Space_complexity . podział zestawu na miejsce wymaga tylko O ​​(1) dodatkowej przestrzeni - nie liniowej. W ustawieniach przesyłania strumieniowego byłoby to O (k) dodatkowe miejsce, jednak pierwotne pytanie nie wspomina o przesyłaniu strumieniowym.
FuzzyTree,

Nie bezpośrednio, ale pisze: „musisz zeskanować dane wejściowe w O (N), ale możesz przechwycić tylko niewielką ilość informacji (zdefiniowanych w kategoriach k nie N)”, co jest zwykle definicją przesyłania strumieniowego. Przeniesienie wszystkich liczb do partycjonowania nie jest tak naprawdę możliwe, chyba że masz tablicę rozmiaru N. Po prostu pytanie zawiera wiele odpowiedzi, które wydają się ignorować to ograniczenie.
Thomas Ahle,

1
Ale jak mówisz, wydajność może spadać w miarę dodawania kolejnych liczb? Możemy również użyć algorytmu liniowej mediany czasu, aby zawsze uzyskać idealne cięcie, ale jeśli liczby k są dobrze rozłożone w 1, ..., n, nie musisz przechodzić przez poziomy dziennika „głębokie”, zanim będziesz mógł przycinać jakieś oddziały?
Thomas Ahle,

2
Najgorszym czasem działania jest rzeczywiście nlogk, ponieważ musisz przetworzyć całe dane wejściowe co najwyżej razy logk, a następnie jest to sekwencja geometryczna (taka, która zaczyna się od co najwyżej n elementów). Wymagania dotyczące miejsca są rejestrowane, gdy są implementowane przy użyciu zwykłej rekurencji, ale można je ustawić O (1), uruchamiając rzeczywisty szybki wybór i zapewniając prawidłową długość każdej partycji.
emu

7

Oto rozwiązanie, które wykorzystuje k bitów dodatkowej pamięci, bez żadnych sprytnych sztuczek i po prostu proste. Czas wykonania O (n), dodatkowa spacja O (k). Aby udowodnić, że można to rozwiązać bez uprzedniego zapoznania się z rozwiązaniem lub bez geniuszu:

void puzzle (int* data, int n, bool* extra, int k)
{
    // data contains n distinct numbers from 1 to n + k, extra provides
    // space for k extra bits. 

    // Rearrange the array so there are (even) even numbers at the start
    // and (odd) odd numbers at the end.
    int even = 0, odd = 0;
    while (even + odd < n)
    {
        if (data [even] % 2 == 0) ++even;
        else if (data [n - 1 - odd] % 2 == 1) ++odd;
        else { int tmp = data [even]; data [even] = data [n - 1 - odd]; 
               data [n - 1 - odd] = tmp; ++even; ++odd; }
    }

    // Erase the lowest bits of all numbers and set the extra bits to 0.
    for (int i = even; i < n; ++i) data [i] -= 1;
    for (int i = 0; i < k; ++i) extra [i] = false;

    // Set a bit for every number that is present
    for (int i = 0; i < n; ++i)
    {
        int tmp = data [i];
        tmp -= (tmp % 2);
        if (i >= even) ++tmp;
        if (tmp <= n) data [tmp - 1] += 1; else extra [tmp - n - 1] = true;
    }

    // Print out the missing ones
    for (int i = 1; i <= n; ++i)
        if (data [i - 1] % 2 == 0) printf ("Number %d is missing\n", i);
    for (int i = n + 1; i <= n + k; ++i)
        if (! extra [i - n - 1]) printf ("Number %d is missing\n", i);

    // Restore the lowest bits again.
    for (int i = 0; i < n; ++i) {
        if (i < even) { if (data [i] % 2 != 0) data [i] -= 1; }
        else { if (data [i] % 2 == 0) data [i] += 1; }
    }
}

Chciałeś (data [n - 1 - odd] % 2 == 1) ++odd;?
Charles

2
Czy możesz wyjaśnić, jak to działa? Nie rozumiem.
Teepeemm

Rozwiązanie byłoby bardzo, bardzo proste, gdybym mógł użyć tablicy boolanów (n + k) do tymczasowego przechowywania, ale nie jest to dozwolone. Dlatego zmieniam układ danych, umieszczając liczby parzyste na początku, a liczby nieparzyste na końcu tablicy. Teraz najniższe bity z tych liczb n mogą być użyte do tymczasowego przechowywania, ponieważ wiem, ile jest liczb parzystych i nieparzystych i mogę odtworzyć najniższe bity! Te n bitów i k dodatkowych bitów to dokładnie (n + k) booleany, których potrzebowałem.
gnasher729

2
To nie zadziałałoby, gdyby dane były zbyt duże, aby utrzymać je w pamięci, a Ty widziałeś to tylko jako strumień. Cudownie zrzędliwy :)
Thomas Ahle,

Złożoność przestrzeni może wynosić O (1). W pierwszym przejściu wszystkie liczby <(n - k) przetwarzane są dokładnie przez ten algorytm, bez użycia „dodatkowego”. W drugim przejściu ponownie usuwasz bity parzystości i używasz pierwszych k pozycji do indeksowania liczb (nk) .. (n).
emu

5

Czy możesz sprawdzić, czy każdy numer istnieje? Jeśli tak, możesz spróbować:

S = suma wszystkich liczb w torbie (S <5050)
Z = suma brakujących liczb 5050 - S

jeśli brakujące liczby to, xa ynastępnie:

x = Z - y i
max (x) = Z - 1

Sprawdzasz więc zakres od 1do max(x)i znajdujesz numer


1
Co max(x)oznacza, kiedy xjest liczbą?
Thomas Ahle,

2
prawdopodobnie oznacza on maksimum z zestawu liczb
JavaHopper

jeśli mamy więcej niż 2 liczby, to rozwiązanie zostałoby wyeliminowane
ozgeneral

4

Być może ten algorytm może działać dla pytania 1:

  1. Oblicz wstępnie xor pierwszych 100 liczb całkowitych (val = 1 ^ 2 ^ 3 ^ 4 .... 100)
  2. x lub elementy, które wciąż pochodzą ze strumienia wejściowego (val1 = val1 ^ next_input)
  3. ostateczna odpowiedź = val ^ val1

Lub nawet lepiej:

def GetValue(A)
  val=0
  for i=1 to 100
    do
      val=val^i
    done
  for value in A:
    do
      val=val^value 
    done
  return val

Algorytm ten można w rzeczywistości rozszerzyć o dwie brakujące liczby. Pierwszy krok pozostaje taki sam. Kiedy wywołamy GetValue z dwoma brakującymi numerami, wynikiem będzie a a1^a2to dwie brakujące liczby. Powiedzmy

val = a1^a2

Teraz, aby przesiać a1 i a2 z val, bierzemy dowolny ustawiony bit w val. Powiedzmy, że ithbit jest ustawiony na val. Oznacza to, że a1 i a2 mają różną parzystość w ithpozycji bitu. Teraz wykonujemy kolejną iterację oryginalnej tablicy i zachowujemy dwie wartości xor. Jeden dla liczb z ustawionym i-tym bitem i drugi, który nie ma ustawionego i-tego bitu. Mamy teraz dwa segmenty liczb i ich gwarancje, które a1 and a2będą znajdować się w różnych segmentach. Teraz powtórz to samo, co zrobiliśmy, aby znaleźć jeden brakujący element na każdym wiadrze.


To tylko rozwiązuje problem k=1, prawda? Ale lubię używać xorsum, wydaje się to nieco szybsze.
Thomas Ahle,

@ThomasAhle Tak. Wywołałem to w mojej odpowiedzi.
bashrc

Dobrze. Czy masz pojęcie, czym może być xor „drugiego rzędu” dla k = 2? Podobnie do używania kwadratów do sumowania, czy moglibyśmy „kwadrat” dla xor?
Thomas Ahle

1
@ThomasAhle Zmodyfikowano, aby działał dla 2 brakujących liczb.
bashrc

to mój ulubiony sposób :)
Robert King

3

Możesz rozwiązać Q2, jeśli masz sumę obu list i iloczyn obu list.

(l1 to oryginał, l2 to zmodyfikowana lista)

d = sum(l1) - sum(l2)
m = mul(l1) / mul(l2)

Możemy to zoptymalizować, ponieważ suma szeregu arytmetycznego jest n razy średnia z pierwszego i ostatniego wyrażenia:

n = len(l1)
d = (n/2)*(n+1) - sum(l2)

Teraz wiemy, że (jeśli a i b to usunięte liczby):

a + b = d
a * b = m

Możemy więc zmienić układ:

a = s - b
b * (s - b) = m

I pomnóż:

-b^2 + s*b = m

I przegrupuj, aby prawa strona miała zero:

-b^2 + s*b - m = 0

Następnie możemy rozwiązać formułę kwadratową:

b = (-s + sqrt(s^2 - (4*-1*-m)))/-2
a = s - b

Przykładowy kod Python 3:

from functools import reduce
import operator
import math
x = list(range(1,21))
sx = (len(x)/2)*(len(x)+1)
x.remove(15)
x.remove(5)
mul = lambda l: reduce(operator.mul,l)
s = sx - sum(x)
m = mul(range(1,21)) / mul(x)
b = (-s + math.sqrt(s**2 - (-4*(-m))))/-2
a = s - b
print(a,b) #15,5

Nie znam złożoności funkcji sqrt, zmniejszania i sumowania, więc nie mogę obliczyć złożoności tego rozwiązania (jeśli ktoś wie, proszę o komentarz poniżej).


Ile czasu i pamięci wykorzystuje do obliczenia x1*x2*x3*...?
Thomas Ahle,

@ThomasAhle Jest to czas O (n) i O (1) na długości listy, ale w rzeczywistości jest to więcej, ponieważ mnożenie (przynajmniej w Pythonie) to czas O (n ^ 1.6) na długości liczba i liczby mają długość O (log n).
Tuomas Laakkonen

@ThomasAhle Nie, log (a ^ n) = n * log (a), abyś miał O (l log k) -spacja do przechowywania numeru. Biorąc pod uwagę listę długości l i oryginalne liczby długości k, miałbyś spację O (l), ale stały współczynnik (log k) byłby niższy niż zwykłe wypisanie ich wszystkich. (Nie sądzę, że moja metoda jest szczególnie dobrym sposobem na udzielenie odpowiedzi na pytanie.)
Tuomas Laakkonen

3

W przypadku Q2 jest to rozwiązanie, które jest nieco bardziej nieefektywne niż inne, ale nadal ma środowisko wykonawcze O (N) i zajmuje miejsce O (k).

Chodzi o to, aby uruchomić oryginalny algorytm dwa razy. W pierwszym otrzymujesz brakującą liczbę całkowitą, co daje górną granicę brakujących liczb. Zadzwońmy na ten numer N. Wiesz, że brakujące dwie liczby będą sumować się N, więc pierwsza liczba może być w przedziale, [1, floor((N-1)/2)]podczas gdy druga będzie [floor(N/2)+1,N-1].

W ten sposób ponownie zapętlasz wszystkie liczby, odrzucając wszystkie liczby, które nie są uwzględnione w pierwszym przedziale. Tymi, którzy śledzą ich sumę. Wreszcie poznasz jedną z brakujących dwóch liczb, a przez to drugą.

Mam wrażenie, że tę metodę można uogólnić i być może wielokrotne wyszukiwania przebiegają równolegle podczas jednego przejścia nad danymi wejściowymi, ale nie wiem, jak to zrobić.


Ahaha tak, to jest to samo rozwiązanie, które wymyśliłem dla Q2, tylko z ponownym obliczeniem sumy przyjmując negatywy dla wszystkich liczb poniżej N / 2, ale to jest jeszcze lepsze!
xjcl

2

Myślę, że można tego dokonać bez skomplikowanych równań i teorii matematycznych. Poniżej znajduje się propozycja rozwiązania złożoności czasowej i czasowej O (2n):

Założenia formularza wejściowego:

Liczba liczb w torbie = n

Liczba brakujących liczb = k

Liczby w torbie są reprezentowane przez tablicę długości n

Długość tablicy wejściowej dla algo = n

Brakujące wpisy w tablicy (liczby wyjęte z torby) są zastępowane wartością pierwszego elementu w tablicy.

Na przykład. Początkowo torba wygląda jak [2,9,3,7,8,6,4,5,1,10]. Jeśli 4 zostanie wyjęte, wartość 4 stanie się 2 (pierwszy element tablicy). Dlatego po wyjęciu 4 torba będzie wyglądać następująco [2,9,3,7,8,6,2,5,1,10]

Kluczem do tego rozwiązania jest oznaczenie INDEKSU odwiedzanej liczby poprzez zanegowanie wartości w tym INDEKSIE podczas przemierzania tablicy.

    IEnumerable<int> GetMissingNumbers(int[] arrayOfNumbers)
    {
        List<int> missingNumbers = new List<int>();
        int arrayLength = arrayOfNumbers.Length;

        //First Pass
        for (int i = 0; i < arrayLength; i++)
        {
            int index = Math.Abs(arrayOfNumbers[i]) - 1;
            if (index > -1)
            {
                arrayOfNumbers[index] = Math.Abs(arrayOfNumbers[index]) * -1; //Marking the visited indexes
            }
        }

        //Second Pass to get missing numbers
        for (int i = 0; i < arrayLength; i++)
        {                
            //If this index is unvisited, means this is a missing number
            if (arrayOfNumbers[i] > 0)
            {
                missingNumbers.Add(i + 1);
            }
        }

        return missingNumbers;
    }

To zużywa zbyt dużo pamięci.
Thomas Ahle,

2

Istnieje ogólny sposób na uogólnienie takich algorytmów przesyłania strumieniowego. Chodzi o to, aby zastosować odrobinę randomizacji, aby, mam nadzieję, „rozłożyć” kelementy na niezależne problemy podrzędne, w których nasz oryginalny algorytm rozwiązuje problem za nas. Technikę tę stosuje się między innymi w rzadkiej rekonstrukcji sygnału.

  • Zrób tablicę ao rozmiarze u = k^2.
  • Wybrać dowolny uniwersalny funkcji skrótu , h : {1,...,n} -> {1,...,u}. (Jak wielokrotne zmiany )
  • Dla każdego iz 1, ..., nwzrostema[h(i)] += i
  • Dla każdej liczby xw strumieniu wejściowym zmniejsz a[h(x)] -= x.

Jeśli wszystkie brakujące liczby zostały połączone w różne segmenty, niezerowe elementy tablicy będą teraz zawierać brakujące liczby.

Prawdopodobieństwo wysłania określonej pary do tego samego segmentu jest mniejsze niż 1/uz definicji uniwersalnej funkcji skrótu. Ponieważ istnieją k^2/2pary, mamy prawdopodobieństwo, że błąd jest co najwyżej k^2/2/u=1/2. Oznacza to, że odniesiemy sukces z prawdopodobieństwem co najmniej 50%, a jeśli zwiększymy u, zwiększymy nasze szanse.

Zauważ, że ten algorytm zajmuje k^2 lognbity przestrzeni (Potrzebujemy lognbitów na segment łyżki.) Odpowiada to przestrzeni wymaganej przez odpowiedź @Dimitris Andreou (W szczególności wymaganie miejsca faktoryzacji wielomianowej, które zdarza się również losowo.) Ten algorytm ma również stałą czas na aktualizację, a nie czas kw przypadku sum mocy.

W rzeczywistości możemy być jeszcze bardziej wydajni niż metoda sumy mocy, stosując sztuczkę opisaną w komentarzach.


Uwaga: Możemy również użyć xorw każdym segmencie, a nie sum, jeśli jest to szybsze na naszej maszynie.
Thomas Ahle

Ciekawe, ale myślę, że przestrzega to ograniczenia przestrzeni tylko wtedy, gdy k <= sqrt(n)- przynajmniej jeśli u=k^2? Załóżmy, że k = 11 i n = 100, wtedy miałbyś 121 segmentów, a algorytm byłby podobny do tablicy 100 bitów, którą sprawdzasz podczas odczytywania każdego # ze strumienia. Zwiększenie uzwiększa szanse na sukces, ale istnieje limit, o ile możesz go zwiększyć, zanim przekroczysz ograniczenie przestrzeni.
FuzzyTree

1
Problem ma sens w nznacznie większym stopniu niż k, jak sądzę, ale w rzeczywistości można uzyskać miejsce k lognza pomocą metody bardzo podobnej do opisanej funkcji mieszania, przy jednoczesnym ciągłym aktualizowaniu czasu. Jest to opisane w gnunet.org/eppstein-set-reconciliation , podobnie jak metoda sumy mocy, ale w zasadzie masz skrót do „dwóch z k” segmentów z silną funkcją skrótu, taką jak haszowanie tabelaryczne, co gwarantuje, że niektóre segmenty będą miały tylko jeden element . Aby zdekodować, identyfikujesz to wiadro i usuwa element z obu jego wiader, co (prawdopodobnie) uwalnia kolejne wiadro i tak dalej
Thomas Ahle

2

Bardzo proste rozwiązanie Q2, które, jestem zaskoczony, nikt jeszcze nie odpowiedział. Użyj metody z Q1, aby znaleźć sumę dwóch brakujących liczb. Oznaczmy to jako S, wtedy jedna z brakujących liczb jest mniejsza niż S / 2, a druga większa niż S / 2 (duh). Zsumuj wszystkie liczby od 1 do S / 2 i porównaj je z wynikiem formuły (podobnie do metody z Q1), aby znaleźć niższą wartość między brakującymi liczbami. Odejmij go od S, aby znaleźć większą brakującą liczbę.


Myślę, że jest to to samo, co odpowiedź Svalorzena , ale wyjaśniłeś to dokładniej. Masz pomysł, jak uogólnić to na Qk?
John McClane

Przepraszamy za brak drugiej odpowiedzi. Nie jestem pewien, czy można uogólnić go na $ Q_k $, ponieważ w takim przypadku nie można powiązać najmniejszego brakującego elementu z pewnym zakresem. Wiesz, że jakiś element musi być mniejszy niż $ S / k $, ale może to dotyczyć wielu elementów
Gilad Deutsch

1

Bardzo fajny problem. Postanowiłbym użyć różnicy ustawionej dla Qk. Wiele języków programowania ma nawet obsługę tego, na przykład w Ruby:

missing = (1..100).to_a - bag

Prawdopodobnie nie jest to najbardziej wydajne rozwiązanie, ale skorzystałbym z niego w prawdziwym życiu, gdyby w tym przypadku stanęło mi przed takim zadaniem (znane granice, niskie granice). Jeśli zestaw liczb byłby bardzo duży, rozważałbym oczywiście bardziej wydajny algorytm, ale do tego czasu proste rozwiązanie byłoby dla mnie wystarczające.


1
To zajmuje zbyt dużo miejsca.
Thomas Ahle,

@ThomasAhle: Dlaczego dodajesz bezużyteczne komentarze do co drugiej odpowiedzi? Co masz na myśli mówiąc, że zajmuje zbyt dużo miejsca?
DarkDust

Ponieważ pytanie brzmi: „Nie możemy sobie pozwolić na dodatkowe miejsce proporcjonalne do N.” To rozwiązanie robi dokładnie to.
Thomas Ahle,

1

Możesz spróbować użyć filtra Bloom . Wstaw każdą liczbę do torby w rozkwicie, a następnie powtarzaj cały zestaw 1-k, aż zgłosisz, że nie znaleziono żadnej z nich. To może nie znaleźć odpowiedzi we wszystkich scenariuszach, ale może być wystarczająco dobrym rozwiązaniem.


Istnieje również filtr liczenia kwitnienia, który umożliwia usunięcie. Następnie możesz po prostu dodać wszystkie liczby i usunąć te, które widzisz w strumieniu.
Thomas Ahle,

Haha, to prawdopodobnie jedna z bardziej praktycznych odpowiedzi, ale mało uwagi.
ldog

1

Przyjąłem inne podejście do tego pytania i zbadałem ankietera, aby uzyskać więcej informacji na temat większego problemu, który próbuje rozwiązać. W zależności od problemu i otaczających go wymagań, oczywiste rozwiązanie oparte na zestawie może być właściwe, a podejście polegające na generowaniu listy i wybieraniu go później może nie być właściwe.

Na przykład może się zdarzyć, że osoba przeprowadzająca wywiad wyśle nwiadomości i musi wiedzieć, kktóre nie przyniosły odpowiedzi, i musi wiedzieć o tym w jak najkrótszym czasie naściennym po otrzymaniu n-kodpowiedzi. Powiedzmy również, że natura kanału komunikatów jest taka, że ​​nawet przy pełnym otwarciu jest wystarczająco dużo czasu na wykonanie przetwarzania między komunikatami bez wpływu na to, ile czasu zajmuje uzyskanie wyniku końcowego po otrzymaniu ostatniej odpowiedzi. Czas ten może zostać wykorzystany na wstawienie jakiegoś identyfikującego elementu każdej wysłanej wiadomości do zestawu i usunięcie go wraz z nadejściem każdej odpowiadającej odpowiedzi. Po otrzymaniu ostatniej odpowiedzi jedyne, co należy zrobić, to usunąć jego identyfikator z zestawu, co w typowych implementacjach wymagaO(log k+1). Następnie zestaw zawiera listę kbrakujących elementów i nie trzeba wykonywać żadnego dodatkowego przetwarzania.

To z pewnością nie jest najszybsze podejście do przetwarzania partii wstępnie wygenerowanych pakietów liczb, ponieważ wszystko działa O((log 1 + log 2 + ... + log n) + (log n + log n-1 + ... + log k)). Ale działa dla dowolnej wartości k(nawet jeśli nie jest znana z góry), aw powyższym przykładzie został zastosowany w sposób, który minimalizuje najbardziej krytyczny interwał.


Czy to zadziałałoby, gdybyś miał tylko dodatkową pamięć O (k ^ 2)?
Thomas Ahle,

1

Możesz motywować rozwiązanie, myśląc o nim w kategoriach symetrii (grupy, w języku matematyki). Bez względu na kolejność zbioru liczb odpowiedź powinna być taka sama. Jeśli zamierzasz użyć kfunkcji do ustalenia brakujących elementów, powinieneś pomyśleć o tym, jakie funkcje mają tę właściwość: symetryczną. Funkcja s_1(x) = x_1 + x_2 + ... + x_njest przykładem funkcji symetrycznej, ale są też inne o wyższym stopniu. W szczególności rozważ podstawowe elementarne funkcje symetryczne . Elementarną funkcją symetryczną stopnia 2 jest s_2(x) = x_1 x_2 + x_1 x_3 + ... + x_1 x_n + x_2 x_3 + ... + x_(n-1) x_nsuma wszystkich iloczynów dwóch elementów. Podobnie dla elementarnych funkcji symetrycznych stopnia 3 i wyższych. Są oczywiście symetryczne. Co więcej, okazuje się, że są one elementami składowymi wszystkich funkcji symetrycznych.

Zauważ, że możesz budować podstawowe funkcje symetryczne s_2(x,x_(n+1)) = s_2(x) + s_1(x)(x_(n+1)). Dalsze przemyślenia powinny cię przekonać s_3(x,x_(n+1)) = s_3(x) + s_2(x)(x_(n+1))i tak dalej, aby można je było obliczyć za jednym razem.

Jak rozpoznać, których elementów brakowało w tablicy? Pomyśl o wielomianu (z-x_1)(z-x_2)...(z-x_n). Ocenia, 0czy wpiszesz którąś z liczb x_i. Rozwijając wielomian, otrzymujesz z^n-s_1(x)z^(n-1)+ ... + (-1)^n s_n. Pojawiają się tutaj również elementarne funkcje symetryczne, co naprawdę nie jest zaskoczeniem, ponieważ wielomian powinien pozostać taki sam, jeśli zastosujemy jakąkolwiek permutację do pierwiastków.

Możemy więc zbudować wielomian i spróbować go uwzględnić, aby dowiedzieć się, które liczby nie są w zbiorze, jak wspomnieli inni.

W końcu, jeśli mamy do czynienia o przepełnieniu pamięci z dużą liczbą (n-ty wielomian symetryczny będzie rzędu 100!), możemy wykonać te obliczenia mod p, gdzie pjest głównym większy niż 100. W tym przypadku mamy do oceny wielomian mod pi uważają, że ponownie ocenia do 0kiedy wejście jest liczbą w zestawie i zwraca wartość niezerową, gdy wejście jest liczbą nie w zestawie. Jednak, jak zauważyli inni, aby uzyskać wartości z wielomianu w czasie, który zależy od k, nie Nmusimy uwzględniać wielomianu mod p.


1

Jeszcze innym sposobem jest użycie filtrowania wykresu szczątkowego.

Załóżmy, że mamy cyfry od 1 do 4 i brakuje 3. Reprezentacja binarna jest następująca:

1 = 001b, 2 = 010b, 3 = 011b, 4 = 100b

I mogę utworzyć schemat blokowy jak poniżej.

                   1
             1 -------------> 1
             |                | 
      2      |     1          |
0 ---------> 1 ----------> 0  |
|                          |  |
|     1            1       |  |
0 ---------> 0 ----------> 0  |
             |                |
      1      |      1         |
1 ---------> 0 -------------> 1

Zauważ, że wykres przepływu zawiera x węzłów, zaś x oznacza liczbę bitów. A maksymalna liczba krawędzi to (2 * x) -2.

Tak więc dla 32-bitowej liczby całkowitej zajmie miejsce O (32) lub miejsce O (1).

Teraz, jeśli usunę pojemność dla każdej liczby, zaczynając od 1,2,4, pozostanie mi wykres resztkowy.

0 ----------> 1 ---------> 1

W końcu uruchomię pętlę taką jak poniżej,

 result = []
 for x in range(1,n):
     exists_path_in_residual_graph(x)
     result.append(x)

Teraz wynik resultzawiera liczby, których również nie brakuje (fałszywie dodatnie). Ale k <= (rozmiar wyniku) <= n, gdy kbrakuje elementów.

Przejdę podaną listę po raz ostatni, aby zaznaczyć brakujący wynik lub nie.

Złożoność czasowa będzie więc O (n).

Wreszcie możliwe jest zmniejszenie liczby fałszywie dodatnich (i wymaganej przestrzeni) poprzez węzły 00, 01, 11, 10zamiast po prostu 0i 1.


Nie rozumiem twojego wykresu. Co oznaczają węzły, krawędzie i liczby? Dlaczego niektóre krawędzie są skierowane, a inne nie?
Dain

W rzeczywistości tak naprawdę nie rozumiem twojej odpowiedzi, czy możesz wyjaśnić coś więcej?
Dain

1

Prawdopodobnie potrzebujesz wyjaśnienia, co oznacza O (k).

Oto banalne rozwiązanie dla dowolnego k: dla każdego v w zbiorze liczb kumuluj sumę 2 ^ v. Na końcu pętla i od 1 do N. Jeśli suma bitowa AND z 2 ^ i wynosi zero, to brakuje i. (Lub liczbowo, jeśli dolna część sumy podzielonej przez 2 ^ i jest parzysta. Or sum modulo 2^(i+1)) < 2^i.)

Łatwe, prawda? Czas O (N), pamięć O (1) i obsługuje dowolne k.

Tyle że obliczasz ogromne liczby, które na prawdziwym komputerze wymagałyby przestrzeni O (N). W rzeczywistości to rozwiązanie jest identyczne z wektorem bitowym.

Więc możesz być sprytny i obliczyć sumę i sumę kwadratów i sumę kostek ... aż do sumy v ^ k, i wykonać fantazyjną matematykę, aby uzyskać wynik. Ale to także duże liczby, co nasuwa pytanie: o jakim abstrakcyjnym modelu działania mówimy? Ile wpasowuje się w przestrzeń O (1) i ile czasu zajmuje zsumowanie liczb dowolnej wielkości?


Niezła odpowiedź! Jedna mała rzecz: „Jeśli suma modulo 2 ^ i wynosi zero, to brakuje mi i” jest niepoprawna. Ale jasne jest, co jest zamierzone. Myślę, że „jeśli suma modulo 2 ^ (i + 1) jest mniejsza niż 2 ^ i, to brakuje mi i” byłoby poprawne. (Oczywiście w większości języków programowania używamy przesunięcia bitowego zamiast obliczeń modulo. Czasami języki programowania są nieco bardziej wyraziste niż zwykła notacja matematyczna. :-))
jcsahnwaldt mówi GoFundMonica

1
Dzięki, masz całkowitą rację! Naprawiono, chociaż byłem leniwy i zboczyłem z notacji matematycznej ... och, i też to popsułem. Naprawiam ponownie ...
sfink

1

Oto rozwiązanie, które nie opiera się na złożonej matematyce, jak robią to odpowiedzi sdcvvc / Dimitris Andreou, nie zmienia tablicy wejściowej tak, jak zrobili to caf i pułkownik Panic, i nie używa zestawu bitów o ogromnych rozmiarach, jak Chris Lercher, JeremyP i wiele innych zrobiło. Zasadniczo zacząłem od pomysłu Svalorzen / Gilada Deutcha na drugi kwartał, uogólniłem go na wspólny przypadek Qk i zaimplementowałem w Javie, aby udowodnić, że algorytm działa.

Pomysł

Załóżmy, że mamy dowolny przedział I, o którym wiemy tylko, że zawiera on co najmniej jedną z brakujących liczb. Po jednym przejściu przez tablicę wejściowego, patrząc tylko na numerach od I , można otrzymać zarówno sumy S , a ilość Q brakujących numerów z I . Robimy to po prostu zmniejszając długość I za każdym razem, gdy napotykamy liczbę od I (dla uzyskania Q ) i zmniejszając z góry obliczoną sumę wszystkich liczb w I o tę napotkaną liczbę za każdym razem (dla uzyskania S ).

Teraz patrzymy na S i Q . Jeśli Q = 1 , oznacza to, że wówczas , że zawiera tylko jeden z brakujących numerów, a ta liczba jest wyraźnie S . Oznaczamy I jako ukończony (w programie nazywa się to „jednoznacznym”) i nie uwzględniamy go w dalszych rozważaniach. Z drugiej strony, gdy Q> 1 , można obliczyć średnią A = S / P brakujących numerów zawartych w I . Ponieważ wszystkie liczby są różne, co najmniej jeden z tych numerów jest mniejsze niż A i co najmniej jeden jest większy od A . Teraz podzieliliśmy I na A.na dwa mniejsze przedziały, z których każdy zawiera co najmniej jedną brakującą liczbę. Zauważ, że nie ma znaczenia, do których przedziałów przypisujemy A, jeśli jest to liczba całkowita.

Wykonujemy kolejny przebieg tablicowy, obliczając S i Q osobno dla każdego z przedziałów (ale w tym samym przebiegu), a następnie zaznaczamy przedziały dla Q = 1 i przedziały podziału dla Q> 1 . Kontynuujemy ten proces, dopóki nie pojawią się nowe „dwuznaczne” przedziały, tzn. Nie mamy nic do podzielenia, ponieważ każdy przedział zawiera dokładnie jedną brakującą liczbę (i zawsze znamy tę liczbę, ponieważ znamy S ). Zaczynamy od jedynego przedziału „całego zakresu” zawierającego wszystkie możliwe liczby (np. [1..N] w pytaniu).

Analiza złożoności czasu i przestrzeni

Całkowita liczba przejść p, które musimy wykonać, aż do zatrzymania procesu, nigdy nie jest większa niż liczba brakujących liczb k . Nierówność p <= k można udowodnić rygorystycznie. Z drugiej strony istnieje również empiryczna górna granica p <log 2 N + 3, która jest przydatna dla dużych wartości k . Musimy przeprowadzić wyszukiwanie binarne dla każdej liczby tablicy wejściowej, aby określić przedział, do którego ona należy. Dodaje to mnożnik log k do złożoności czasu.

W sumie złożoność czasu wynosi O (N ᛫ min (k, log N) ᛫ log k) . Zauważ, że w przypadku dużego k jest to znacznie lepsze niż w przypadku metody sdcvvc / Dimitris Andreou, czyli O (N ᛫ k) .

Do swojej pracy algorytm wymaga O (k) dodatkowej przestrzeni do przechowywania w większości k przedziałów, która jest znacznie lepsza niż O (N) w rozwiązaniach „zestawu bitów”.

Implementacja Java

Oto klasa Java, która implementuje powyższy algorytm. Zawsze zwraca posortowaną tablicę brakujących liczb. Poza tym nie wymaga liczenia brakujących liczb k, ponieważ oblicza go w pierwszym przejściu. Cały zakres liczb jest podany przez parametry minNumberi maxNumber(np. 1 i 100 dla pierwszego przykładu w pytaniu).

public class MissingNumbers {
    private static class Interval {
        boolean ambiguous = true;
        final int begin;
        int quantity;
        long sum;

        Interval(int begin, int end) { // begin inclusive, end exclusive
            this.begin = begin;
            quantity = end - begin;
            sum = quantity * ((long)end - 1 + begin) / 2;
        }

        void exclude(int x) {
            quantity--;
            sum -= x;
        }
    }

    public static int[] find(int minNumber, int maxNumber, NumberBag inputBag) {
        Interval full = new Interval(minNumber, ++maxNumber);
        for (inputBag.startOver(); inputBag.hasNext();)
            full.exclude(inputBag.next());
        int missingCount = full.quantity;
        if (missingCount == 0)
            return new int[0];
        Interval[] intervals = new Interval[missingCount];
        intervals[0] = full;
        int[] dividers = new int[missingCount];
        dividers[0] = minNumber;
        int intervalCount = 1;
        while (true) {
            int oldCount = intervalCount;
            for (int i = 0; i < oldCount; i++) {
                Interval itv = intervals[i];
                if (itv.ambiguous)
                    if (itv.quantity == 1) // number inside itv uniquely identified
                        itv.ambiguous = false;
                    else
                        intervalCount++; // itv will be split into two intervals
            }
            if (oldCount == intervalCount)
                break;
            int newIndex = intervalCount - 1;
            int end = maxNumber;
            for (int oldIndex = oldCount - 1; oldIndex >= 0; oldIndex--) {
                // newIndex always >= oldIndex
                Interval itv = intervals[oldIndex];
                int begin = itv.begin;
                if (itv.ambiguous) {
                    // split interval itv
                    // use floorDiv instead of / because input numbers can be negative
                    int mean = (int)Math.floorDiv(itv.sum, itv.quantity) + 1;
                    intervals[newIndex--] = new Interval(mean, end);
                    intervals[newIndex--] = new Interval(begin, mean);
                } else
                    intervals[newIndex--] = itv;
                end = begin;
            }
            for (int i = 0; i < intervalCount; i++)
                dividers[i] = intervals[i].begin;
            for (inputBag.startOver(); inputBag.hasNext();) {
                int x = inputBag.next();
                // find the interval to which x belongs
                int i = java.util.Arrays.binarySearch(dividers, 0, intervalCount, x);
                if (i < 0)
                    i = -i - 2;
                Interval itv = intervals[i];
                if (itv.ambiguous)
                    itv.exclude(x);
            }
        }
        assert intervalCount == missingCount;
        for (int i = 0; i < intervalCount; i++)
            dividers[i] = (int)intervals[i].sum;
        return dividers;
    }
}

Dla uczciwości klasa ta otrzymuje dane wejściowe w postaci NumberBagobiektów. NumberBagnie zezwala na modyfikację tablicy i losowy dostęp, a także liczy, ile razy tablica była wymagana do sekwencyjnego przechodzenia. Jest również bardziej odpowiedni do testowania dużych tablic niż Iterable<Integer>dlatego, że pozwala uniknąć intpakowania pierwotnych wartości i pozwala na zawijanie części dużego int[]dla wygodnego przygotowania testu. To nie jest trudne do zastąpienia, w razie potrzeby, NumberBagprzez int[]lub Iterable<Integer>wpisać findpodpis, zmieniając dwie pętle dla w nim na te foreach.

import java.util.*;

public abstract class NumberBag {
    private int passCount;

    public void startOver() {
        passCount++;
    }

    public final int getPassCount() {
        return passCount;
    }

    public abstract boolean hasNext();

    public abstract int next();

    // A lightweight version of Iterable<Integer> to avoid boxing of int
    public static NumberBag fromArray(int[] base, int fromIndex, int toIndex) {
        return new NumberBag() {
            int index = toIndex;

            public void startOver() {
                super.startOver();
                index = fromIndex;
            }

            public boolean hasNext() {
                return index < toIndex;
            }

            public int next() {
                if (index >= toIndex)
                    throw new NoSuchElementException();
                return base[index++];
            }
        };
    }

    public static NumberBag fromArray(int[] base) {
        return fromArray(base, 0, base.length);
    }

    public static NumberBag fromIterable(Iterable<Integer> base) {
        return new NumberBag() {
            Iterator<Integer> it;

            public void startOver() {
                super.startOver();
                it = base.iterator();
            }

            public boolean hasNext() {
                return it.hasNext();
            }

            public int next() {
                return it.next();
            }
        };
    }
}

Testy

Proste przykłady demonstrujące użycie tych klas podano poniżej.

import java.util.*;

public class SimpleTest {
    public static void main(String[] args) {
        int[] input = { 7, 1, 4, 9, 6, 2 };
        NumberBag bag = NumberBag.fromArray(input);
        int[] output = MissingNumbers.find(1, 10, bag);
        System.out.format("Input: %s%nMissing numbers: %s%nPass count: %d%n",
                Arrays.toString(input), Arrays.toString(output), bag.getPassCount());

        List<Integer> inputList = new ArrayList<>();
        for (int i = 0; i < 10; i++)
            inputList.add(2 * i);
        Collections.shuffle(inputList);
        bag = NumberBag.fromIterable(inputList);
        output = MissingNumbers.find(0, 19, bag);
        System.out.format("%nInput: %s%nMissing numbers: %s%nPass count: %d%n",
                inputList, Arrays.toString(output), bag.getPassCount());

        // Sieve of Eratosthenes
        final int MAXN = 1_000;
        List<Integer> nonPrimes = new ArrayList<>();
        nonPrimes.add(1);
        int[] primes;
        int lastPrimeIndex = 0;
        while (true) {
            primes = MissingNumbers.find(1, MAXN, NumberBag.fromIterable(nonPrimes));
            int p = primes[lastPrimeIndex]; // guaranteed to be prime
            int q = p;
            for (int i = lastPrimeIndex++; i < primes.length; i++) {
                q = primes[i]; // not necessarily prime
                int pq = p * q;
                if (pq > MAXN)
                    break;
                nonPrimes.add(pq);
            }
            if (q == p)
                break;
        }
        System.out.format("%nSieve of Eratosthenes. %d primes up to %d found:%n",
                primes.length, MAXN);
        for (int i = 0; i < primes.length; i++)
            System.out.format(" %4d%s", primes[i], (i % 10) < 9 ? "" : "\n");
    }
}

Testowanie dużej tablicy można wykonać w ten sposób:

import java.util.*;

public class BatchTest {
    private static final Random rand = new Random();
    public static int MIN_NUMBER = 1;
    private final int minNumber = MIN_NUMBER;
    private final int numberCount;
    private final int[] numbers;
    private int missingCount;
    public long finderTime;

    public BatchTest(int numberCount) {
        this.numberCount = numberCount;
        numbers = new int[numberCount];
        for (int i = 0; i < numberCount; i++)
            numbers[i] = minNumber + i;
    }

    private int passBound() {
        int mBound = missingCount > 0 ? missingCount : 1;
        int nBound = 34 - Integer.numberOfLeadingZeros(numberCount - 1); // ceil(log_2(numberCount)) + 2
        return Math.min(mBound, nBound);
    }

    private void error(String cause) {
        throw new RuntimeException("Error on '" + missingCount + " from " + numberCount + "' test, " + cause);
    }

    // returns the number of times the input array was traversed in this test
    public int makeTest(int missingCount) {
        this.missingCount = missingCount;
        // numbers array is reused when numberCount stays the same,
        // just Fisher–Yates shuffle it for each test
        for (int i = numberCount - 1; i > 0; i--) {
            int j = rand.nextInt(i + 1);
            if (i != j) {
                int t = numbers[i];
                numbers[i] = numbers[j];
                numbers[j] = t;
            }
        }
        final int bagSize = numberCount - missingCount;
        NumberBag inputBag = NumberBag.fromArray(numbers, 0, bagSize);
        finderTime -= System.nanoTime();
        int[] found = MissingNumbers.find(minNumber, minNumber + numberCount - 1, inputBag);
        finderTime += System.nanoTime();
        if (inputBag.getPassCount() > passBound())
            error("too many passes (" + inputBag.getPassCount() + " while only " + passBound() + " allowed)");
        if (found.length != missingCount)
            error("wrong result length");
        int j = bagSize; // "missing" part beginning in numbers
        Arrays.sort(numbers, bagSize, numberCount);
        for (int i = 0; i < missingCount; i++)
            if (found[i] != numbers[j++])
                error("wrong result array, " + i + "-th element differs");
        return inputBag.getPassCount();
    }

    public static void strideCheck(int numberCount, int minMissing, int maxMissing, int step, int repeats) {
        BatchTest t = new BatchTest(numberCount);
        System.out.println("╠═══════════════════════╬═════════════════╬═════════════════╣");
        for (int missingCount = minMissing; missingCount <= maxMissing; missingCount += step) {
            int minPass = Integer.MAX_VALUE;
            int passSum = 0;
            int maxPass = 0;
            t.finderTime = 0;
            for (int j = 1; j <= repeats; j++) {
                int pCount = t.makeTest(missingCount);
                if (pCount < minPass)
                    minPass = pCount;
                passSum += pCount;
                if (pCount > maxPass)
                    maxPass = pCount;
            }
            System.out.format("║ %9d  %9d  ║  %2d  %5.2f  %2d  ║  %11.3f    ║%n", missingCount, numberCount, minPass,
                    (double)passSum / repeats, maxPass, t.finderTime * 1e-6 / repeats);
        }
    }

    public static void main(String[] args) {
        System.out.println("╔═══════════════════════╦═════════════════╦═════════════════╗");
        System.out.println("║      Number count     ║      Passes     ║  Average time   ║");
        System.out.println("║   missimg     total   ║  min  avg   max ║ per search (ms) ║");
        long time = System.nanoTime();
        strideCheck(100, 0, 100, 1, 20_000);
        strideCheck(100_000, 2, 99_998, 1_282, 15);
        MIN_NUMBER = -2_000_000_000;
        strideCheck(300_000_000, 1, 10, 1, 1);
        time = System.nanoTime() - time;
        System.out.println("╚═══════════════════════╩═════════════════╩═════════════════╝");
        System.out.format("%nSuccess. Total time: %.2f s.%n", time * 1e-9);
    }
}

Wypróbuj je na Ideone


0

Uważam, że mam algorytm O(k)czasu i O(log(k))przestrzeni, biorąc pod uwagę, że masz dostępne funkcje floor(x)i log2(x)dla dowolnie dużych liczb całkowitych:

Masz k-bitową liczbę całkowitą (stąd log8(k)spację), do której dodajesz x^2, gdzie x to kolejny numer znaleziony w torbie: s=1^2+2^2+...Zajmuje to trochę O(N)czasu (co nie jest problemem dla ankietera). Na koniec dostajesz j=floor(log2(s))największą liczbę, której szukasz. Następnie s=s-ji ponownie wykonaj powyższe czynności:

for (i = 0 ; i < k ; i++)
{
  j = floor(log2(s));
  missing[i] = j;
  s -= j;
}

Teraz zwykle nie masz funkcji floor i log2 dla 2756liczb całkowitych -bit, ale zamiast podwójnych. Więc? Po prostu dla każdego 2 bajtów (lub 1, 3, lub 4) możesz użyć tych funkcji, aby uzyskać pożądane liczby, ale to dodaje O(N)czynnik do złożoności czasu


0

Może to zabrzmieć głupio, ale w pierwszym przedstawionym problemie musiałbyś zobaczyć wszystkie pozostałe liczby w torbie, aby je właściwie dodać, aby znaleźć brakującą liczbę za pomocą tego równania.

Ponieważ widzisz wszystkie liczby, po prostu znajdź brakującą liczbę. To samo dotyczy braku dwóch liczb. Myślę, że całkiem proste. Nie ma sensu używać równania, gdy zobaczysz liczby pozostające w torbie.


2
Myślę, że zaletą ich podsumowania jest to, że nie musisz pamiętać, które liczby już widziałeś (np. Nie ma dodatkowego zapotrzebowania na pamięć). W przeciwnym razie jedyną opcją jest zachowanie zestawu wszystkich widocznych wartości, a następnie powtórzenie tego zestawu ponownie, aby znaleźć tę, której brakuje.
Dan Tao,

3
To pytanie jest zwykle zadawane przy założeniu złożoności przestrzeni O (1).

Suma pierwszych N liczb to N (N + 1) / 2. Dla N = 100 suma = 100 * (101) / 2 = 5050;
tmarthal

0

Myślę, że można to uogólnić w następujący sposób:

Oznacz S, M jako wartości początkowe dla sumy szeregów arytmetycznych i mnożenia.

S = 1 + 2 + 3 + 4 + ... n=(n+1)*n/2
M = 1 * 2 * 3 * 4 * .... * n 

Powinienem pomyśleć o formule do obliczenia tego, ale nie o to chodzi. W każdym razie, jeśli brakuje jednego numeru, już podałeś rozwiązanie. Jeśli jednak brakuje dwóch liczb, oznaczmy nową sumę i całkowitą wielokrotność przez S1 i M1, które będą następujące:

S1 = S - (a + b)....................(1)

Where a and b are the missing numbers.

M1 = M - (a * b)....................(2)

Ponieważ znasz S1, M1, M i S, powyższe równanie można rozwiązać, aby znaleźć aib, brakujące liczby.

Teraz brakuje trzech liczb:

S2 = S - ( a + b + c)....................(1)

Where a and b are the missing numbers.

M2 = M - (a * b * c)....................(2)

Teraz twoje nieznane wynosi 3, podczas gdy masz tylko dwa równania, z których możesz rozwiązać.


Mnożenie staje się jednak dość duże. Jak generalizujesz do więcej niż 2 brakujących liczb?
Thomas Ahle,

Próbowałem tych wzorów na bardzo prostej sekwencji z N = 3 i brakujących liczb = {1, 2}. Nie działałem, ponieważ uważam, że błąd występuje we wzorach (2), które należy przeczytać M1 = M / (a * b)(zobacz tę odpowiedź ). To działa dobrze.
dma_k,

0

Nie wiem, czy to jest skuteczne, czy nie, ale chciałbym zaproponować to rozwiązanie.

  1. Oblicz xor 100 elementów
  2. Oblicz xor z 98 elementów (po usunięciu 2 elementów)
  3. Teraz (wynik 1) XOR (wynik 2) daje ci xor dwóch brakujących nosów i..ea XOR b, jeśli a i b są brakującymi elementami
    4. Uzyskaj sumę brakujących numerów przy zwykłym podejściu do suma formuły diff i powiedzmy, że diff to d.

Teraz uruchom pętlę, aby uzyskać możliwe pary (p, q), z których obie leżą w [1, 100] i sumują do d.

Po uzyskaniu pary sprawdź, czy (wynik 3) XOR p = q i jeśli tak, to koniec.

Popraw mnie, jeśli się mylę, a także skomentuj złożoność czasu, jeśli jest to poprawne


2
Nie sądzę, aby suma i xor jednoznacznie definiowały dwie liczby. Uruchomienie pętli w celu uzyskania wszystkich możliwych k-krotek, które sumują się do d, zajmuje czas O (C (n, k-1)) = O (n <sup> k-1 </sup>), co dla k> 2 jest zły.
Teepeemm

0

Możemy wykonać Q1 i Q2 w O (log n) przez większość czasu.

Załóżmy, że nasza memory chipskłada się z tablicy nliczb test tubes. A liczba xw probówce jest reprezentowana przez x milliliterciecz chemiczną.

Załóżmy, że nasz procesor to laser light. Kiedy zapalamy laser, przechodzi on przez wszystkie rury prostopadle do jego długości. Za każdym razem, gdy przechodzi przez ciecz chemiczną, jasność jest zmniejszana o 1. Przekazywanie światła przy pewnym znaku mililitra jest działaniem O(1).

Teraz, jeśli zapalimy nasz laser na środku probówki i uzyskamy moc świetlną

  • jest równa wstępnie obliczonej wartości (obliczanej, gdy nie brakuje żadnych liczb), wówczas brakujące liczby są większe niż n/2.
  • Jeśli nasza wydajność jest mniejsza, oznacza to, że brakuje co najmniej jednej liczby, która jest mniejsza niż n/2. Możemy również sprawdzić, czy jasność jest zmniejszona o 1lub 2. jeśli zostanie zmniejszona do 1tego czasu, jedna brakująca liczba jest mniejsza niż, n/2a inna jest większa niż n/2. Jeśli zmniejszy się o 2to, obie liczby są mniejsze niż n/2.

Możemy powtórzyć powyższy proces wielokrotnie i zawężając naszą domenę problemów. Na każdym etapie zmniejszamy domenę o połowę. I wreszcie możemy dojść do naszego wyniku.

Równoległe algorytmy, o których warto wspomnieć (ponieważ są interesujące),

  • sortowanie według jakiegoś algorytmu równoległego, na przykład scalenie równoległe może być wykonane w O(log^3 n)czasie. A następnie brakującą liczbę można znaleźć na podstawie wyszukiwania binarnego w O(log n)czasie.
  • Teoretycznie, jeśli mamy nprocesory, to każdy proces może sprawdzić jedno z danych wejściowych i ustawić flagę identyfikującą liczbę (dogodnie w tablicy). I w następnym kroku każdy proces może sprawdzić każdą flagę i ostatecznie wypisać liczbę, która nie jest oflagowana. Cały proces zajmie trochę O(1)czasu. Ma dodatkowe O(n)zapotrzebowanie na miejsce / pamięć.

Należy zauważyć, że dwa równoległe algorytmy przedstawione powyżej mogą wymagać dodatkowej przestrzeni, jak wspomniano w komentarzu .


Chociaż metoda lasera z probówką jest naprawdę interesująca, mam nadzieję, że zgadzasz się z tym, że nie przekłada się ona dobrze na instrukcje sprzętowe, a więc raczej nie jest O(logn)na komputerze.
SirGuy,

1
Jeśli chodzi o twoją metodę sortowania, zajmie to dodatkową przestrzeń, która zależy Nod O(N)czasu i więcej niż czasu (pod względem jego zależności N), od którego zamierzamy zrobić lepiej niż.
SirGuy,

@ SirGuy Doceniam twoje obawy dotyczące koncepcji probówki i kosztu pamięci przetwarzania równoległego. Mój post ma na celu podzielenie się przemyśleniami na temat problemu. Procesory GPU wykonują teraz przetwarzanie równoległe. Kto wie, jeśli koncepcja probówki nie będzie dostępna w przyszłości.
shuva,
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.