Znajdź liczbę całkowitą nie spośród czterech miliardów podanych

Statystycznie poinformowane algorytmy rozwiązują ten problem przy użyciu mniejszej liczby przejść niż deterministyczne podejścia.

Jeśli dozwolone są bardzo duże liczby całkowite , można wygenerować liczbę, która prawdopodobnie będzie unikalna w czasie O(1). Pseudolosowa 128-bitowa liczba całkowita, taka jak GUID , zderzy się tylko z jedną z istniejących czterech miliardów liczb całkowitych w zestawie w mniej niż jednej na każde 64 miliardy miliardów przypadków.

Jeśli liczby całkowite są ograniczone do 32 bitów , to jeden może wygenerować liczbę, która może być unikalna w jednym przejściu, używając znacznie mniej niż 10 MB. Prawdopodobieństwo zderzenia pseudolosowej 32-bitowej liczby całkowitej z jedną z 4 miliardów istniejących liczb całkowitych wynosi około 93% (4e9 / 2^32). Szanse, że 1000 pseudolosowych liczb całkowitych zderzy się, są mniejsze niż 1 na 12 000 miliardów miliardów miliardów (szanse na jedną kolizję ^ 1000). Więc jeśli program utrzymuje strukturę danych zawierającą 1000 pseudolosowych kandydatów i iteracje poprzez znane liczby całkowite, eliminując dopasowania od kandydatów, to wszystko, ale pewne jest, aby znaleźć co najmniej jedną liczbę całkowitą, która nie jest w pliku.

Szczegółowe omówienie tego problemu zostało omówione w Jon Bentley "Kolumna 1. Cracking the Oyster " Programowanie Perły Addison-Wesley pp. 3-10

Bentley omawia kilka podejść, w tym sortowanie zewnętrzne, sortowanie scalające przy użyciu kilku zewnętrznych plików itp., Ale najlepszą metodą, jaką Bentley sugeruje, jest algorytm pojedynczego przejścia wykorzystujący pola bitowe , który humorystycznie nazywa " Wonder Sort" :) Idąc do problemu, 4 miliardy liczb może być reprezentowany w:

4 billion bits = (4000000000 / 8) bytes = about 0.466 GB

Kod do implementacji bitsetu jest prosty: (zaczerpnięty ze strony rozwiązań )

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];

void set(int i) {        a[i>>SHIFT] |=  (1<<(i & MASK)); }
void clr(int i) {        a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int  test(int i){ return a[i>>SHIFT] &   (1<<(i & MASK)); }

Algorytm Bentleya wykonuje jedno przejście nad plikiem, set ting odpowiedni bit w tablicy, a następnie bada tę tablicę za pomocą makra test powyżej, aby znaleźć brakującą liczbę.

Jeśli dostępna pamięć jest mniejsza niż 0,466 GB, Bentley sugeruje algorytm k-pass, który dzieli Dane wejściowe na zakresy w zależności od dostępnej pamięci. Aby wziąć bardzo prosty przykład, jeśli tylko 1 bajt (tj. pamięć do obsługi 8 liczb ) była dostępna i zakres wynosił od 0 do 31, dzielimy to na zakresy od 0 do 7, 8-15, 16-22 i tak dalej i obsługujemy ten zakres w każdym z 32/8 = 4 przejść.

HTH.

Ponieważ problem nie określa, że musimy znaleźć najmniejszą możliwą liczbę, która nie znajduje się w pliku, możemy po prostu wygenerować liczbę, która jest dłuższa niż sam plik wejściowy. :)

Dla wariantu 1 GB RAM można użyć wektora bitowego. Musisz przeznaczyć 4 miliardy bitów = = 500 MB bajtów tablicy. Dla każdej liczby odczytanej z wejścia ustaw odpowiedni bit na '1'. Gdy już to zrobisz, wykonaj iterację nad bitami, znajdź pierwszy, który nadal jest '0'. Jego indeks jest odpowiedzią.

Jeśli są 32-bitowymi liczbami całkowitymi (prawdopodobnie z wyboru ~4 miliardów liczb bliskich 2^32), Twoja lista 4 miliardów liczb zajmie maksymalnie 93% możliwych liczb całkowitych (4 * 10^9 / (2^32) ). Jeśli więc utworzysz tablicę bitową 2^32 bitów z każdym bitem inicjalizowanym do zera (która zajmie 2^29 bajtów ~ 500 MB PAMIĘCI RAM; pamiętaj bajt = 2^3 bity = 8 bitów), przeczytaj listę liczb całkowitych i dla każdej int ustaw odpowiedni element tablicy bitów od 0 do 1; a następnie przeczytaj przez swoją listę bit-array i zwraca pierwszy bit, który jest nadal 0.

W przypadku, gdy masz mniej pamięci RAM (~10 MB), To rozwiązanie musi zostać nieco zmodyfikowane. 10 MB ~ 83886080 bitów wciąż wystarcza do wykonania tablicy bitów dla wszystkich liczb od 0 do 83886079. Możesz więc przeczytać swoją listę ints; i tylko rekord #s, które są między 0 a 83886079 w tablicy bitów. Jeśli liczby są losowo rozmieszczone; z przytłaczającym prawdopodobieństwem (różni się o 100% o 10^-2592069) będziesz Znajdź brakujący int). W rzeczywistości, jeśli tylko wybrać numery od 1 do 2048 (z 256 bajtów) można jeszcze znaleźć brakującą liczbę przytłaczający procent (99.9999999999999999999999999999999999999999999999999999999999995%) czasu.

Ale powiedzmy, że zamiast mieć około 4 miliardów liczb; miałeś coś w rodzaju 2^32 - 1 liczb i mniej niż 10 MB PAMIĘCI RAM; więc każdy mały zakres ints ma tylko małą możliwość nie zawiera liczby.

If you were guaranteed że każda int na liście jest unikalna, można zsumować Liczby i odjąć sumę z jednym # brakującym do pełnej sumy (1/2)(2^32)(2^32 - 1) = 9223372034707292160 aby znaleźć brakujące int. Jednakże, jeśli int wystąpił dwukrotnie, ta metoda nie powiedzie się.

Jednak zawsze można dzielić i rządzić. Naiwną metodą byłoby odczytanie tablicy i policzenie liczby liczb, które są w pierwszej połowie (0 do 2^31-1) i w drugiej połowie (2^31, 2^32). Następnie wybierz zakres z mniej liczb i powtórz dzieląc ten zakres na pół. (Powiedzmy, że gdyby w (2^31, 2^32) było o dwie liczby mniej, to twoje następne wyszukiwanie policzyłoby liczby w zakresie (2^31, 3*2^30-1), (3*2^30, 2^32). Powtarzaj, aż znajdziesz zakres z liczbami zerowymi i masz swoją odpowiedź. Powinna przyjmować O (lg N) ~ 32 odczytów przez tablicę.

import numpy as np
nums_in_bin = np.zeros(65536, dtype=np.uint32)
for N in four_billion_int_array:
    nums_in_bin[N // 65536] += 1
for bin_num, bin_count in enumerate(nums_in_bin):
    if bin_count < 65536:
        break # we have found an incomplete bin with missing ints (bin_num)

Przeczytaj listę ~4 miliardów liczb całkowitych; i policz, ile wejść przypada w każdym z pojemników 2^16 i znajdź niekompletny_bin, który nie ma wszystkich 65536 liczby. Następnie ponownie czytasz listę 4 miliardów liczb całkowitych; ale tym razem zauważ tylko, gdy liczby całkowite są w tym zakresie; przerzucanie trochę, gdy je znajdziesz.

del nums_in_bin # allow gc to free old 256kB array
from bitarray import bitarray
my_bit_array = bitarray(65536) # 32 kB
my_bit_array.setall(0)
for N in four_billion_int_array:
    if N // 65536 == bin_num:
        my_bit_array[N % 65536] = 1
for i, bit in enumerate(my_bit_array):
    if not bit:
        print bin_num*65536 + i
        break

Dlaczego to takie skomplikowane? Prosisz o liczbę całkowitą nieobecną w pliku?

Zgodnie z określonymi regułami, jedyną rzeczą, którą musisz zapisać, jest największa liczba całkowita, którą napotkałeś do tej pory w pliku. Po wczytaniu całego pliku Zwraca liczbę 1 większą od tej.

Nie ma ryzyka trafienia maxint lub czegokolwiek, ponieważ zgodnie z zasadami, nie ma ograniczeń co do wielkości liczby całkowitej lub liczby zwracanej przez algorytm.

Można to rozwiązać w bardzo małej przestrzeni za pomocą wariantu wyszukiwania binarnego.

1. Zacznij od dozwolonego zakresu liczb, 0 do 4294967295.

2. Oblicz punkt środkowy.

3. Pętla przez plik, licząc ile liczb było równych, mniej lub więcej niż wartość punktu środkowego.

4. Jeśli żadne liczby nie są równe, jesteś skończony. Środkowy Numer jest odpowiedzią.

5. W przeciwnym razie wybierz zakres, który miał najmniej Liczby i powtórz z kroku 2 z tym nowym zakresem.

Będzie to wymagało do 32 skanów liniowych przez plik, ale będzie używać tylko kilku bajtów pamięci do przechowywania zakresu i zliczania.

EDIT Ok, to nie było do końca przemyślane, ponieważ zakłada, że liczby całkowite w pliku podążają za jakąś statyczną dystrybucją. Widocznie nie muszą, ale nawet wtedy należy spróbować tego:

Istnieje ≈4,3 miliarda 32-bitowych liczb całkowitych. Nie wiemy, w jaki sposób są one rozmieszczone w pliku, ale najgorszy przypadek to ten o najwyższej entropii Shannona: równy rozkład. W tym przypadku prawdopodobieństwo, że jedna liczba całkowita nie wystąpi w pliku to

( (2³²-1)/2³² )⁴ ⁰⁰⁰ ⁰⁰⁰ ⁰⁰⁰ ≈ .4

Im niższa Entropia Shannona, tym większe prawdopodobieństwo, ale nawet w tym najgorszym przypadku mamy szansę 90% na znalezienie nieokreślonej liczby po 5 zgadnięciach z losowymi liczbami całkowitymi. Wystarczy utworzyć takie liczby za pomocą generatora pseudorandomu, zapisać je na liście. Następnie przeczytaj int po int i porównaj go ze wszystkimi domysłami. Gdy jest dopasowanie, usuń ten wpis na liście. Po przejrzeniu wszystkich plików, są szanse, że będziesz mieć więcej niż jeden / align = "left" / Użyj któregokolwiek z nich. W rzadkim (10% nawet w najgorszym przypadku) przypadku braku zgadywania, uzyskaj nowy zestaw losowych liczb całkowitych, być może więcej tym razem (10 - >99%).

Zużycie pamięci: kilkadziesiąt bajtów, złożoność: O (n), overhead: necleable ponieważ większość czasu będzie spędzana w nieuniknionym dostępie do dysku twardego, a nie porównywanie i tak ints.

Jeśli brakuje jednej liczby całkowitej w zakresie [0, 2^x - 1] więc prześlij je wszystkie razem. Na przykład:

>>> 0 ^ 1 ^ 3
2
>>> 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 6 ^ 7
5

(wiem, że to nie odpowiada dokładnie na pytanie , ale jest to dobra odpowiedź na bardzo podobne pytanie.)

Na podstawie obecnego sformułowania w pytaniu pierwotnym najprostszym rozwiązaniem jest:

Znajdź maksymalną wartość w pliku, a następnie dodaj do niego 1.

Mogą się zastanawiać, czy słyszałeś o probabilistycznym filtrze Bloom , który może bardzo skutecznie określić, czy wartość nie jest częścią dużego zbioru, (ale może określić tylko z dużym prawdopodobieństwem, że jest członkiem zbioru.)

Użyj BitSet. 4 miliardy liczb całkowitych (przy założeniu do 2^32 liczb całkowitych) upakowanych w BitSet o wartości 8 na bajt jest 2^32 / 2^3 = 2^29 = ok. 0,5 Gb.

Aby dodać nieco więcej szczegółów-za każdym razem, gdy czytasz liczbę, ustaw odpowiedni bit W Zestawie bitów. Następnie wykonaj przejście nad zestawem bitów, aby znaleźć pierwszą liczbę, która nie jest obecna. W rzeczywistości możesz to zrobić równie skutecznie, wielokrotnie wybierając losową liczbę i sprawdzając, czy jest ona obecna.

Właściwie BitSet.nextClearBit (0) powie jesteś pierwszym niezaangażowanym kawałkiem.

Patrząc na BitSet API, wydaje się, że obsługuje tylko 0..MAX_INT, więc możesz potrzebować 2 Bitsetów - jeden dla liczb + 've i jeden dla -' VE-ale wymagania dotyczące pamięci się nie zmieniają.

Jeśli nie ma limitu rozmiaru, najszybszym sposobem jest pobranie długości pliku i wygenerowanie długości pliku+1 liczba losowych cyfr (lub po prostu "11111..."s). Zaleta: nie trzeba nawet czytać pliku i można zminimalizować zużycie pamięci prawie do zera. Wada: wydrukujesz miliardy cyfr.

Jednakże, gdyby jedynym czynnikiem było minimalizowanie zużycia pamięci i nic innego nie jest ważne, byłoby to optymalne rozwiązanie. Może nawet doprowadzić do " najgorszego nadużycia w Regulamin".

Jeśli założymy, że zakres liczb zawsze będzie wynosił 2^n (parzysta moc 2), to exclusive-or będzie działać (jak pokazano na innym plakacie). Jeśli chodzi o dlaczego, udowodnijmy to:

Teoria

Biorąc pod uwagę dowolny zakres liczb całkowitych oparty na 0, w którym brakuje elementów 2^n, można znaleźć brakujący element po prostu XOR-ing znanych wartości razem, aby uzyskać brakującą liczbę.

Dowód

Spójrzmy na n = 2. Dla n=2 możemy reprezentować 4 unikalne liczby całkowite: 0, 1, 2, 3. Mają wzór bitowy:

• 0 - 00
• 1 - 01
• 2 - 10
• 3 - 11

Teraz, jeśli spojrzymy, każdy bit jest ustawiony dokładnie dwa razy. Dlatego, ponieważ jest ustawiona parzysta liczba razy, i wyłączne-lub liczb daje 0. Jeśli brakuje pojedynczej liczby, wyłączna-lub Da liczbę, która gdy wyłączna-lub z brakującą liczbą spowoduje 0. Dlatego brakujący numer i wynikowe liczby wyłączne są dokładnie takie same. Jeśli usuniemy 2, otrzymany xor będzie 10 (lub 2).

Dlatego, ponieważ n=2 działa, a n+1 działa, metoda xor będzie działać dla wszystkich wartości n>=2.

Algorytm Dla Zakresów Bazujących Na 0

long supplied = 0;
long result = 0;
while (supplied = read_int_from_file()) {
    result = result ^ supplied;
}
return result;

Algorytm Dla Dowolnych Zakresów Bazowych

Algorytm ten będzie działał dla zakresy dowolnej liczby początkowej do dowolnej liczby końcowej, o ile całkowity zakres jest równy 2^n... To zasadniczo zmienia zakres, aby mieć minimum na 0. Ale to wymaga 2 przechodzi przez plik(pierwszy, aby pobrać minimum, drugi, aby obliczyć brakującą int).

long supplied = 0;
long result = 0;
long offset = INT_MAX;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    result = result ^ (supplied - offset);
}
return result + offset;

Dowolne Zakresy

Możemy zastosować tę zmodyfikowaną metodę do zbioru dowolnych zakresów, ponieważ wszystkie zakresy przekroczą moc 2^n co najmniej raz. Działa to tylko wtedy, gdy brakuje jednego trochę. Pobiera 2 przejazdy nieposortowanego pliku, ale za każdym razem znajdzie brakującą liczbę:

long supplied = 0;
long result = 0;
long offset = INT_MAX;
long n = 0;
double temp;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    n++;
    result = result ^ (supplied - offset);
}
// We need to increment n one value so that we take care of the missing 
// int value
n++
while (n == 1 || 0 != (n & (n - 1))) {
    result = result ^ (n++);
}
return result + offset;

Zasadniczo, ponownie bazuje zakres wokół 0. Następnie zlicza liczbę niesortowanych wartości do dodania, obliczając ekskluzywne-or. Następnie dodaje 1 do liczby niesortowanych wartości, aby zająć się brakującą wartością(policzyć brakującą). Następnie zachowaj xoring wartości N, zwiększanej za każdym razem o 1, aż N będzie potęgą 2. Wynik jest następnie oparty z powrotem do pierwotnej bazy. Załatwione.

Oto algorytm, który przetestowałem w PHP (używając tablicy zamiast pliku, ale tej samej koncepcji):

function find($array) {
    $offset = min($array);
    $n = 0;
    $result = 0;
    foreach ($array as $value) {
        $result = $result ^ ($value - $offset);
        $n++;
    }
    $n++; // This takes care of the missing value
    while ($n == 1 || 0 != ($n & ($n - 1))) {
        $result = $result ^ ($n++);
    }
    return $result + $offset;
}

Umieszczony w tablicy z dowolnym zakresem wartości (testowałem w tym negatywy) z jednym wewnątrz tego zakresu, który jest brakujący, znalazł poprawną wartość za każdym razem.

Inne Podejście

Ponieważ możemy użyć sortowania zewnętrznego, dlaczego po prostu nie sprawdzić luki? Jeśli założymy, że plik jest sortowany przed uruchomieniem tego algorytmu:

long supplied = 0;
long last = read_int_from_file();
while (supplied = read_int_from_file()) {
    if (supplied != last + 1) {
        return last + 1;
    }
    last = supplied;
}
// The range is contiguous, so what do we do here?  Let's return last + 1:
return last + 1;

Sprawdź Rozmiar pliku wejściowego, a następnie wypisz dowolną liczbę , która jest zbyt duża, aby mogła być reprezentowana przez plik o takim rozmiarze.To może wydawać się tanią sztuczką, ale jest kreatywnym rozwiązaniem problemu z wywiadem, starannie pomija problem pamięci i technicznie jest O (n).

void maxNum(ulong filesize)
{
    ulong bitcount = filesize * 8; //number of bits in file

    for (ulong i = 0; i < bitcount; i++)
    {
        Console.Write(9);
    }
}

Powinien wydrukować 10 ^bitcount - 1, która zawsze będzie większa niż 2 ^bitcount. Technicznie, liczba, którą musisz pokonać to 2 ^bitcount - (4 * 10⁹ - 1), ponieważ wiesz, że w pliku znajdują się (4 miliardy - 1) inne liczby całkowite, a nawet przy doskonałej kompresji zajmą one co najmniej jeden bit.

Podchwytliwe pytanie, chyba że zostało źle zacytowane. Po prostu przeczytaj plik raz, aby uzyskać maksymalną liczbę całkowitą n i zwróć n+1.

Oczywiście potrzebujesz planu zapasowego na wypadek, gdyby n+1 spowodowało całkowite przepełnienie.

• Najprostszym sposobem jest znalezienie minimalnej liczby w pliku i zwrócenie o 1 mniej. Używa o (1) storage I O (n) time dla pliku n liczb. Jednak nie powiedzie się, jeśli zakres liczb jest ograniczony, co może sprawić, że min-1 nie będzie liczbą.

• Wspomniano już o prostej i prostej metodzie korzystania z bitmapy. Metoda ta wykorzystuje Czas O (n)i przechowywanie.

• Wspomniano również o metodzie 2-pass z 2^16 zliczającymi wiadrami. Odczytuje 2 * n liczb całkowitych, więc używa O(n) czasu i o (1) pamięci masowej, ale nie może obsługiwać zestawów danych z więcej niż 2^16 liczb. Jednak można go łatwo rozszerzyć do (np.) 2^60 64-bitowych liczb całkowitych, uruchamiając 4 przejścia zamiast 2, i łatwo dostosować do korzystania z małej pamięci, używając tylko tyle pojemników, ile mieści się w pamięci i odpowiednio zwiększając liczbę przejść, w którym to przypadku czas wykonywania nie jest już O(n), ale zamiast O (N*log n).

• Metoda XOR ' ING wszystkich liczb razem, wymienione tak far by rfrankel and at length by ircmaxell odpowiada na pytanie zadane w stackoverflow#35185, Jak zauważył ltn100. Używa o (1) storage I O (n) run time. Jeśli na chwilę przyjmiemy 32-bitowe liczby całkowite, XOR ma 7% prawdopodobieństwo wytworzenia odrębnej liczby. Uzasadnienie: podano ~ 4G różnych liczb XOR ' d razem, i ca. 300M Nie w pliku, liczba ustawionych bitów w każdej pozycji bitowej ma równe szanse na nieparzyste lub parzyste. Tak więc liczby 2^32 mają takie samo prawdopodobieństwo powstania jak Wynik XOR, z czego 93% jest już w pliku. Zauważ, że jeśli liczby w pliku nie są różne, prawdopodobieństwo sukcesu metody XOR wzrasta.

Z jakiegoś powodu, jak tylko przeczytałem ten problem, pomyślałem o przekątnej. Zakładam dowolnie duże liczby całkowite.

Przeczytaj pierwszą liczbę. Lewe-pad to z zero bitów, aż masz 4 miliardy bitów. Jeśli pierwszy bit (wysokiego rzędu) wynosi 0, wyjście 1; w przeciwnym razie wyjście 0. (Tak naprawdę nie musisz lewy-pad: po prostu wypisujesz 1, jeśli nie ma wystarczającej ilości bitów w liczbie.) Zrób to samo z drugą liczbą, z wyjątkiem użycia jej drugiego bitu. Kontynuuj przeglądanie Pliku w ten sposób. Będziesz wypisuje 4-miliardowy numer bitowy jeden bit na raz, a liczba ta nie będzie taka sama jak w pliku. Dowód: to było to samo co N-ta liczba, wtedy zgodziliby się na N-ten bit, ale nie przez konstrukcję.

Możesz użyć znaczników bitowych, aby zaznaczyć, czy liczba całkowita jest obecna, czy nie.

Po przejechaniu całego pliku Skanuj każdy bit, aby określić, czy liczba istnieje, czy nie.

Zakładając, że każda liczba całkowita jest 32-bitowa, wygodnie zmieszczą się w 1 GB PAMIĘCI RAM, jeśli bitowe oznaczanie zostanie zakończone.

Tylko dla kompletności, oto kolejne bardzo proste rozwiązanie, które najprawdopodobniej zajmie bardzo dużo czasu, ale zużywa bardzo mało pamięci.

Niech wszystkie możliwe liczby całkowite będą przedziałem od int_min do int_max, oraz bool isNotInFile(integer) funkcja, która zwraca true, jeśli plik nie zawiera pewnej liczby całkowitej i false else (porównując tę pewną liczbę całkowitą z każdą liczbą całkowitą w pliku)

for (integer i = int_min; i <= int_max; ++i)
{
    if (isNotInFile(i)) {
        return i;
    }
}

Dla ograniczenia pamięci 10 MB:

1. Przelicz liczbę na jej binarną reprezentację.
2. Utwórz drzewo binarne, gdzie lewa = 0 i prawa = 1.
3. Wstaw każdą liczbę w drzewie, używając jej reprezentacji binarnej.
4. Jeśli liczba została już wstawiona, liście zostaną już utworzone.

Po zakończeniu, wybierz ścieżkę, która nie została wcześniej utworzona, aby utworzyć żądany numer.

4 miliardy liczb = 2^32, czyli 10 MB może nie wystarczyć.

EDIT

Optymalizacja jest możliwa, jeśli powstały dwa końce i mają wspólny rodzic, to można je usunąć, a rodzic oznaczyć jako rozwiązanie. To tnie gałęzie i zmniejsza potrzebę pamięci.

EDIT II

Nie ma potrzeby, aby budować drzewo całkowicie zbyt. Musisz tylko budować Głębokie gałęzie, jeśli liczby są podobne. Jeśli wyciąć gałęzie też, To rozwiązanie może działać w rzeczywistości.

Usuwa z pliku białe spacje i znaki inne niż numeryczne i dołącza 1. Plik zawiera teraz jeden numer, który nie został wymieniony w oryginalnym pliku.

Odpowiem na wersję 1 GB:

W pytaniu nie ma wystarczającej ilości informacji, więc najpierw przedstawię pewne założenia:

Liczba całkowita to 32 bity o zakresie od -2,147,483,648 do 2,147,483,647.

Pseudo-kod:

var bitArray = new bit[4294967296];  // 0.5 GB, initialized to all 0s.

foreach (var number in file) {
    bitArray[number + 2147483648] = 1;   // Shift all numbers so they start at 0.
}

for (var i = 0; i < 4294967296; i++) {
    if (bitArray[i] == 0) {
        return i - 2147483648;
    }
}

Eliminacja Bitów

Jednym ze sposobów jest wyeliminowanie bitów, jednak może to nie dać rezultatu(są szanse, że nie). Psuedocode:

long val = 0xFFFFFFFFFFFFFFFF; // (all bits set)
foreach long fileVal in file
{
    val = val & ~fileVal;
    if (val == 0) error;
}

Liczba Bitów

Śledź liczbę bitów; i użyj bitów z najmniejszymi kwotami, aby wygenerować wartość. Ponownie nie ma gwarancji wygenerowania prawidłowej wartości.

Range Logic

Śledź listę uporządkowanych zakresów (uporządkowanych według początku). Zakres jest określony przez struktura:

struct Range
{
  long Start, End; // Inclusive.
}
Range startRange = new Range { Start = 0x0, End = 0xFFFFFFFFFFFFFFFF };

Przejrzyj każdą wartość w pliku i spróbuj usunąć ją z bieżącego zakresu. Ta metoda nie ma gwarancji pamięci, ale powinna działać całkiem dobrze.

Tak długo, jak robimy twórcze odpowiedzi, tutaj jest inny.

Użyj zewnętrznego programu sortującego, aby posortować plik wejściowy numerycznie. Będzie to działać dla dowolnej ilości pamięci, którą możesz mieć (w razie potrzeby użyje przechowywania plików). Odczytaj posortowany plik i wypisz brakującą pierwszą liczbę.

2^128*1018 + 1 ( czyli (2⁸)^16*1018 + 1 ) - czy nie może to być uniwersalna odpowiedź na dziś? Oznacza to liczbę, która nie może być przechowywana w pliku 16 EB, który jest maksymalnym rozmiarem pliku w dowolnym bieżącym systemie plików.

Myślę, że jest to rozwiązany problem (patrz wyżej), ale jest ciekawy przypadek poboczny, o którym należy pamiętać, ponieważ może zostać zapytany:

Jeśli są dokładnie 4,294,967,295 (2^32 - 1) 32-bitowe liczby całkowite bez powtórzeń, a zatem brakuje tylko jednego, istnieje proste rozwiązanie.

Uruchom running total od zera i dla każdej liczby całkowitej w pliku dodaj tę liczbę całkowitą z 32-bitowym przepełnieniem (skutecznie, runningTotal = (runningTotal + nextInteger) % 4294967296). Po zakończeniu dodaj 4294967296/2 do sumy uruchomieniowej, ponownie z 32-bitowym przepełnieniem. Odejmij to od 4294967296, a wynikiem będzie brakująca liczba całkowita.

Problem "tylko jednej brakującej liczby całkowitej" można rozwiązać tylko jednym uruchomieniem i tylko 64 bitami pamięci RAM dedykowanymi do danych (32 dla bieżącej liczby całkowitej, 32 do odczytu w następnej liczbie całkowitej).

Następująca: bardziej Ogólna Specyfikacja jest niezwykle prosta do dopasowania, jeśli nie zależy nam na ilości bitów, jakie musi mieć wynik całkowity. Po prostu generujemy na tyle duża liczba całkowita, że nie może być zawarta w podanym pliku. Ponownie zajmuje to absolutnie minimalną ilość pamięci RAM. Zobacz pseudokod.

# Grab the file size
fseek(fp, 0L, SEEK_END);
sz = ftell(fp);
# Print a '2' for every bit of the file.
for (c=0; c<sz; c++) {
  for (b=0; b<4; b++) {
    print "2";
  }
}

Jak to powiedział Ryan, posortuj plik, a następnie przejrzyj liczby całkowite i gdy wartość zostanie pominięta, masz ją :)

EDIT w downvoters: OP wspomniał, że plik można posortować, więc jest to prawidłowa metoda.

Jeśli nie założysz ograniczenia 32-bitowego, po prostu zwróć losowo wygenerowany numer 64-bitowy (lub 128-bitowy, jeśli jesteś pesymistą). Szansa kolizji wynosi 1 in 2^64/(4*10^9) = 4611686018.4 (około 1 na 4 miliardy). Przez większość czasu miałbyś rację!

(żart... tak jakby.)