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

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.

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 ₁ + a ₂ + ... + a _k = b ₁

a ₁ ² + a ₂ ² + ... + a _k ² = b ₂

...

a ₁ ^k + a ₂ ^k + ... + a _k ^k = b _k

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

c ₁ = a ₁ + a ₂ + ... a _k

c ₂ = a ₁ a ₂ + a ₁ a ₃ + ... + a _k-1 a _k

...

c _k = a ₁ a ₂ ... a _k

Jeśli rozszerzysz wielomian (xa ₁ ) ... (xa _k ), współczynniki będą wynosić dokładnie c ₁ , ..., 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 ₁ , ..., 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 ₁ = b ₁ ; c ₂ = (c ₁ b ₁ - b ₂ ) / 2; dokładne formuły można znaleźć w Wikipedii
• Uwzględnij wielomian x ^k -c ₁ x ^k-1 + ... + c _k .
• Korzenie wielomianu to potrzebne liczby a ₁ , ..., _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.

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!).

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.

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ć.

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.

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.

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.

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.

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.

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

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; }
    }
}

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

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.

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).

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ć.

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;
    }

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.

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ę.

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.

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.

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ł.

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.

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.

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?

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 ₂ 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

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

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.

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ć.

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

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 .