Znajdź najmniejszą liczbę całkowitą, której nie ma na liście

Ciekawe pytanie do wywiadu, którego używa mój kolega:

Załóżmy, że otrzymujesz bardzo długą, nieposortowaną listę 64-bitowych liczb całkowitych bez znaku. Jak znaleźć najmniejszą nieujemną liczbę całkowitą, która nie występuje na liście?

KONTROLA: Teraz, gdy zaproponowano oczywiste rozwiązanie polegające na sortowaniu, czy możesz to zrobić szybciej niż O (n log n)?

DALSZE INFORMACJE: Twój algorytm musi działać na komputerze z, powiedzmy, 1 GB pamięci

WYJAŚNIENIE: lista znajduje się w pamięci RAM, chociaż może zużywać jej dużo. Rozmiar listy zostanie podany z góry, powiedzmy N.

Jeśli struktura danych może być zmutowana na miejscu i obsługuje dostęp swobodny, możesz to zrobić w czasie O (N) i O (1) dodatkowej przestrzeni. Po prostu przejrzyj tablicę sekwencyjnie i dla każdego indeksu zapisz wartość w indeksie do indeksu określonego przez wartość, rekurencyjnie umieszczając dowolną wartość w tym miejscu na swoim miejscu i odrzucając wartości> N. Następnie ponownie przejdź przez tablicę w poszukiwaniu miejsca gdzie wartość nie pasuje do indeksu - to najmniejsza wartość spoza tablicy. Daje to co najwyżej 3N porównań i wykorzystuje tylko kilka wartości wartych tymczasowej przestrzeni.

# Pass 1, move every value to the position of its value
for cursor in range(N):
    target = array[cursor]
    while target < N and target != array[target]:
        new_target = array[target]
        array[target] = target
        target = new_target

# Pass 2, find first location where the index doesn't match the value
for cursor in range(N):
    if array[cursor] != cursor:
        return cursor
return N

Oto proste O(N)rozwiązanie, które wykorzystuje O(N)przestrzeń. Zakładam, że ograniczamy listę wejściową do liczb nieujemnych i chcemy znaleźć pierwszą nieujemną liczbę, której nie ma na liście.

1. Znajdź długość listy; powiedzmy, że tak N.
2. Przydziel tablicę Nwartości logicznych, zainicjowaną dla wszystkich false.
3. Dla każdej liczby Xna liście, jeśli Xjest mniejsza niż N, ustaw X'thelement tablicy na true.
4. Przeszukaj tablicę, zaczynając od indeksu 0, szukając pierwszego elementu false. Jeśli znajdziesz pierwszy falsew indeksie I, to Ijest odpowiedź. W przeciwnym razie (tj. Gdy wszystkie elementy są true) odpowiedź brzmi N.

W praktyce „tablica Nwartości logicznych” byłaby prawdopodobnie zakodowana jako „mapa bitowa” lub „zestaw bitów” reprezentowana jako tablica a bytelub int. Zwykle zajmuje to mniej miejsca (w zależności od języka programowania) i pozwala na falseszybsze wykonanie pierwszego skanowania .

Oto jak / dlaczego działa algorytm.

Załóżmy, że Nliczby na liście nie są różne lub że co najmniej jedna z nich jest większa niż N. Oznacza to, że w zakresie musi znajdować się co najmniej jedna liczba, 0 .. N - 1której nie ma na liście. Zatem problem znalezienia najmniejszej brakującej liczby musi zatem sprowadzić się do problemu znalezienia najmniejszej brakującej liczby mniejszej niżN . Oznacza to, że nie musimy śledzić liczb, które są większe lub równe N... ponieważ nie będą one odpowiedzią.

Alternatywą dla poprzedniego akapitu jest to, że lista jest permutacją liczb z 0 .. N - 1. W tym przypadku krok 3 ustawia wszystkie elementy tablicy na true, a krok 4 mówi nam, że pierwsza „brakująca” liczba to N.

Złożoność obliczeniowa algorytmu O(N)charakteryzuje się stosunkowo małą stałą proporcjonalności. Wykonuje dwa liniowe przejścia przez listę lub tylko jeden przebieg, jeśli długość listy zaczyna się od. Nie ma potrzeby reprezentowania całej listy w pamięci, więc asymptotyczne użycie pamięci algorytmu jest potrzebne do reprezentowania tablicy wartości logicznych; czyli O(N)bity.

(Z drugiej strony algorytmy, które opierają się na sortowaniu w pamięci lub partycjonowaniu, zakładają, że można przedstawić całą listę w pamięci. W formie pytania wymagałoby to O(N)64-bitowych słów).

@Jorn komentuje, że kroki od 1 do 3 są odmianą sortowania zliczania. W pewnym sensie ma rację, ale różnice są znaczące:

• Sortowanie według liczenia wymaga tablicy (co najmniej) Xmax - Xminliczników, gdzie Xmaxjest największą liczbą na liście i Xminnajmniejszą liczbą na liście. Każdy licznik musi być w stanie reprezentować N stanów; tj. zakładając reprezentację binarną, musi mieć liczbę całkowitą (przynajmniej) ceiling(log2(N)).
• Aby określić rozmiar tablicy, sortowanie zliczające musi wykonać wstępne przejście przez listę, aby określić Xmaxi Xmin.
• Dlatego też minimalna wymagana ilość miejsca w najgorszym przypadku to ceiling(log2(N)) * (Xmax - Xmin)bity.

Z kolei algorytm przedstawiony powyżej po prostu wymaga Nbitów w najgorszych i najlepszych przypadkach.

Jednak ta analiza prowadzi do intuicji, że gdyby algorytm przeszedł przez listę początkowo szukając zera (i licząc elementy listy, jeśli to konieczne), dałby szybszą odpowiedź, nie wykorzystując w ogóle spacji, gdyby znalazł zero. Zdecydowanie warto to zrobić, jeśli istnieje duże prawdopodobieństwo znalezienia przynajmniej jednego zera na liście. A to dodatkowe przejście nie zmienia ogólnej złożoności.

EDYCJA: Zmieniłem opis algorytmu, aby używał „tablicy wartości logicznych”, ponieważ ludzie najwyraźniej uznali mój oryginalny opis za pomocą bitów i bitmap za mylący.

Ponieważ OP określił teraz, że oryginalna lista jest przechowywana w pamięci RAM, a komputer ma tylko, powiedzmy, 1 GB pamięci, zamierzam wyjść na skraj i przewidzieć, że odpowiedź wynosi zero.

1 GB pamięci RAM oznacza, że ​​lista może zawierać maksymalnie 134 217 728 numerów. Ale jest 2 ⁶⁴ = 18 446 744 073 709 551 616 możliwych liczb. Zatem prawdopodobieństwo, że zero znajduje się na liście, wynosi 1 do 137.438.953.472.

Natomiast moje szanse na porażenie piorunem w tym roku wynoszą 1 na 700 000. A moje szanse na trafienie przez meteoryt wynoszą około 1 na 10 bilionów. Więc jestem około dziesięć razy bardziej prawdopodobne, że zostanę napisany w czasopiśmie naukowym z powodu mojej przedwczesnej śmierci przez ciało niebieskie, niż odpowiedź niezerowa.

Jak wskazano w innych odpowiedziach, możesz zrobić sortowanie, a następnie po prostu skanować, aż znajdziesz lukę.

Możesz zwiększyć złożoność algorytmiczną do O (N) i zachować miejsce O (N), używając zmodyfikowanego QuickSort, w którym eliminujesz partycje, które nie są potencjalnymi kandydatami do wypełnienia luki.

• W pierwszej fazie partycji usuń duplikaty.
• Po zakończeniu partycjonowania spójrz na liczbę elementów w dolnej partycji
• Czy ta wartość jest równa wartości użytej do utworzenia partycji?
  • Jeśli tak, oznacza to, że luka występuje w wyższej partycji.
    • Kontynuuj z quicksort, ignorując dolną partycję
  • W przeciwnym razie luka znajduje się w dolnej przegrodzie
    • Kontynuuj szybkie sortowanie, ignorując wyższą partycję

Oszczędza to dużą liczbę obliczeń.

Aby zilustrować jedną z pułapek O(N)myślenia, oto O(N)algorytm wykorzystujący O(1)przestrzeń.

for i in [0..2^64):
  if i not in list: return i

print "no 64-bit integers are missing"

Ponieważ wszystkie liczby mają 64 bity, możemy na nich zastosować sortowanie radix , czyli O (n). Sortuj je, a następnie skanuj, aż znajdziesz to, czego szukasz.

jeśli najmniejsza liczba to zero, przeszukaj do przodu, aż znajdziesz przerwę. Jeśli najmniejsza liczba nie jest zerem, odpowiedź wynosi zero.

Aby uzyskać metodę efektywną przestrzennie, a wszystkie wartości są różne, możesz to zrobić w O( k )czasie i przestrzeni O( k*log(N)*N ). Zajmuje mało miejsca i nie wymaga przenoszenia danych, a wszystkie operacje są elementarne (dodawanie odejmowania).

1. zestaw U = N; L=0
2. Najpierw podziel przestrzeń liczbową na kregiony. Lubię to:
   • 0->(1/k)*(U-L) + L, 0->(2/k)*(U-L) + L, 0->(3/k)*(U-L) + L...0->(U-L) + L
3. Sprawdź, ile liczb ( count{i}) znajduje się w każdym regionie. ( N*kkroki)
4. Znajdź pierwszy region ( h), który nie jest pełny. To znaczy count{h} < upper_limit{h}. ( kkroki)
5. jeśli h - count{h-1} = 1masz odpowiedź
6. zestaw U = count{h}; L = count{h-1}
7. goto 2

można to poprawić za pomocą haszowania (dzięki Nicowi za ten pomysł).

1. podobnie
2. Najpierw podziel przestrzeń liczbową na kregiony. Lubię to:
   • L + (i/k)->L + (i+1/k)*(U-L)
3. inc count{j} za pomocą j = (number - L)/k (if L < number < U)
4. znajdź pierwszy region ( h), który nie ma w sobie k elementów
5. jeśli count{h} = 1h jest twoją odpowiedzią
6. zestaw U = maximum value in region h L = minimum value in region h

To się pojawi O(log(N)*N).

Po prostu posortuję je, a następnie przeglądam sekwencję, aż znajdę lukę (w tym przerwę na początku między zerem a pierwszą liczbą).

Jeśli chodzi o algorytm, zrobiłoby to coś takiego:

def smallest_not_in_list(list):
    sort(list)
    if list[0] != 0:
        return 0
    for i = 1 to list.last:
        if list[i] != list[i-1] + 1:
            return list[i-1] + 1
    if list[list.last] == 2^64 - 1:
        assert ("No gaps")
    return list[list.last] + 1

Oczywiście, jeśli masz dużo więcej pamięci niż CPU, możesz utworzyć maskę bitową wszystkich możliwych 64-bitowych wartości i po prostu ustawić bity dla każdej liczby na liście. Następnie poszukaj pierwszego 0-bitowego w tej masce bitowej. To zmienia go w operację O (n) pod względem czasu, ale dość cholernie kosztowną pod względem wymagań dotyczących pamięci :-)

Wątpię, czy mógłbyś poprawić O (n), ponieważ nie widzę sposobu, aby to zrobić, który nie wymaga spojrzenia na każdą liczbę przynajmniej raz.

Algorytm dla tego byłby następujący:

def smallest_not_in_list(list):
    bitmask = mask_make(2^64) // might take a while :-)
    mask_clear_all (bitmask)
    for i = 1 to list.last:
        mask_set (bitmask, list[i])
    for i = 0 to 2^64 - 1:
        if mask_is_clear (bitmask, i):
            return i
    assert ("No gaps")

Posortuj listę, spójrz na pierwszy i drugi element i zacznij wspinać się w górę, aż pojawi się luka.

Możesz to zrobić w czasie O (n) i O (1) dodatkowej przestrzeni, chociaż ukryty czynnik jest dość duży. Nie jest to praktyczny sposób rozwiązania problemu, ale może być interesujący.

Dla każdej 64-bitowej liczby całkowitej bez znaku (w porządku rosnącym) iteruj po liście, aż znajdziesz docelową liczbę całkowitą lub dojdziesz do końca listy. Jeśli dojdziesz do końca listy, docelową liczbą całkowitą jest najmniejsza liczba całkowita, której nie ma na liście. Jeśli dojdziesz do końca 64-bitowych liczb całkowitych, każda 64-bitowa liczba całkowita znajduje się na liście.

Tutaj jest to funkcja Pythona:

def smallest_missing_uint64(source_list):
    the_answer = None

    target = 0L
    while target < 2L**64:

        target_found = False
        for item in source_list:
            if item == target:
                target_found = True

        if not target_found and the_answer is None:
            the_answer = target

        target += 1L

    return the_answer

Ta funkcja jest celowo nieefektywna, aby utrzymać ją O (n). Zwróć szczególną uwagę, że funkcja sprawdza docelowe liczby całkowite nawet po znalezieniu odpowiedzi. Jeśli funkcja zwróciłaby się zaraz po znalezieniu odpowiedzi, liczba uruchomień zewnętrznej pętli byłaby ograniczona rozmiarem odpowiedzi, która jest ograniczona przez n. Ta zmiana spowodowałaby, że czas wykonywania O (n ^ 2) byłby dużo szybszy.

Dziękuję egon, swilden i Stephenowi C za inspirację. Po pierwsze, znamy granice wartości celu, ponieważ nie może być ona większa niż rozmiar listy. Ponadto lista o rozmiarze 1 GB może zawierać maksymalnie 134217728 (128 * 2 ^ 20) 64-bitowych liczb całkowitych.

Hashing part
Proponuję użyć haszowania, aby radykalnie zmniejszyć naszą przestrzeń wyszukiwania. Najpierw pierwiastek kwadratowy z wielkości listy. W przypadku listy 1 GB to N = 11 586. Skonfiguruj tablicę liczb całkowitych o rozmiarze N. Powtarzaj listę i weź pierwiastek kwadratowy * z każdej liczby znalezionej jako hash. W swojej tabeli skrótów zwiększ licznik dla tego skrótu. Następnie wykonaj iterację w swojej tabeli skrótów. Pierwszy znaleziony zasobnik, który nie jest równy maksymalnemu rozmiarowi, definiuje nową przestrzeń wyszukiwania.

Część bitmapy
Teraz skonfiguruj zwykłą mapę bitową równą rozmiarowi nowej przestrzeni wyszukiwania i ponownie przejrzyj listę źródeł, wypełniając bitmapę, gdy znajdziesz każdą liczbę w swojej przestrzeni wyszukiwania. Kiedy skończysz, pierwszy nieustawiony bit w twojej mapie bitowej da ci odpowiedź.

Zostanie to zakończone w czasie O (n) i przestrzeni O (sqrt (n)).

(* Możesz użyć czegoś w rodzaju przesunięcia bitowego, aby zrobić to znacznie wydajniej, i po prostu odpowiednio dostosuj liczbę i rozmiar wiader.)

Cóż, jeśli na liście liczb brakuje tylko jednej liczby, najłatwiejszym sposobem znalezienia brakującej liczby jest zsumowanie serii i odjęcie każdej wartości z listy. Ostateczna wartość to brakująca liczba.

 int i = 0;
            while ( i < Array.Length)
            {

                if (Array[i] == i + 1)
                {
                    i++;
                }

                if (i < Array.Length)
                {
                    if (Array[i] <= Array.Length)
                    {//SWap

                        int temp = Array[i];
                        int AnoTemp = Array[temp - 1];
                        Array[temp - 1] = temp;
                        Array[i] = AnoTemp;

                    }
                    else
                       i++;



                }
            }

            for (int j = 0; j < Array.Length; j++)
            {
                if (Array[j] > Array.Length)
                {
                    Console.WriteLine(j + 1);
                    j = Array.Length;
                }
                else
                    if (j == Array.Length - 1)
                        Console.WriteLine("Not Found !!");

            }
        }

Moglibyśmy użyć tablicy haszującej do przechowywania liczb. Gdy wszystkie liczby zostaną wykonane, uruchom licznik od 0, aż znajdziemy najniższą. Dość dobry hash będzie haszował i będzie przechowywany w stałym czasie oraz będzie pobierany w stałym czasie.

for every i in X         // One scan Θ(1)
   hashtable.put(i, i);  // O(1)

low = 0;

while (hashtable.get(i) <> null)   // at most n+1 times
   low++;

print low;

Najgorszy przypadek, jeśli nw tablicy znajdują się elementy i {0, 1, ... n-1}w takim przypadku odpowiedź zostanie uzyskana pod adresem n, nadal ją zachowując O(n).

Oto moja odpowiedź napisana w Javie:

Podstawowy pomysł: 1- Zapętlaj się przez tablicę, wyrzucając zduplikowane liczby dodatnie, zerowe i ujemne, jednocześnie sumując resztę, uzyskując również maksymalną liczbę dodatnią i zachowaj unikalne liczby dodatnie na mapie.

2- Oblicz sumę jako max * (max + 1) / 2.

3- Znajdź różnicę między sumami obliczonymi w krokach 1 i 2

4- Zapętl ponownie od 1 do minimum [sumy różnicy, maks.] I zwróć pierwszą liczbę, której nie ma na mapie wypełnionej w kroku 1.

public static int solution(int[] A) {
    if (A == null || A.length == 0) {
        throw new IllegalArgumentException();
    }

    int sum = 0;
    Map<Integer, Boolean> uniqueNumbers = new HashMap<Integer, Boolean>();
    int max = A[0];
    for (int i = 0; i < A.length; i++) {
        if(A[i] < 0) {
            continue;
        }
        if(uniqueNumbers.get(A[i]) != null) {
            continue;
        }
        if (A[i] > max) {
            max = A[i];
        }
        uniqueNumbers.put(A[i], true);
        sum += A[i];
    }
    int completeSum = (max * (max + 1)) /  2;
    for(int j = 1; j <= Math.min((completeSum - sum), max); j++) {
        if(uniqueNumbers.get(j) == null) { //O(1)
            return j;
        }
    }
    //All negative case
    if(uniqueNumbers.isEmpty()) {
        return 1;
    }
    return 0;
}

Jak sprytnie zauważył Stephen C, odpowiedzią musi być liczba mniejsza niż długość tablicy. Wtedy znalazłbym odpowiedź za pomocą wyszukiwania binarnego. To optymalizuje najgorszy przypadek (więc ankieter nie może złapać cię na patologicznym scenariuszu „co by było, gdyby”). W wywiadzie zwróć uwagę, że robisz to, aby zoptymalizować się pod kątem najgorszego przypadku.

Sposób korzystania z wyszukiwania binarnego polega na odjęciu szukanej liczby od każdego elementu tablicy i sprawdzeniu wyników ujemnych.

Podoba mi się podejście „zgadnij zero”. Jeśli liczby byłyby losowe, zero jest wysoce prawdopodobne. Jeśli „egzaminator” ustawił nielosową listę, dodaj jedną i zgadnij ponownie:

LowNum=0
i=0
do forever {
  if i == N then leave /* Processed entire array */
  if array[i] == LowNum {
     LowNum++
     i=0
     }
   else {
     i++
   }
}
display LowNum

Najgorszym przypadkiem jest n * N gdzie n = N, ale w praktyce n jest bardzo prawdopodobne, że będzie małą liczbą (np. 1)

Nie jestem pewien, czy dostałem pytanie. Ale jeśli dla listy 1, 2, 3, 5, 6 i brakującą liczbą jest 4, to brakującą liczbę można znaleźć w O (n) przez: (n + 2) (n + 1) / 2- (n + 1) nie / 2

EDYCJA: przepraszam, myślę, że myślałem zbyt szybko ostatniej nocy. W każdym razie drugą część należy właściwie zastąpić sumą (listą), czyli miejscem, w którym występuje O (n). Formuła ujawnia ideę: dla n kolejnych liczb całkowitych suma powinna wynosić (n + 1) * n / 2. Jeśli brakuje liczby, suma byłaby równa sumie (n + 1) kolejnych liczb całkowitych minus brakująca liczba.

Dziękuję za zwrócenie uwagi na fakt, że myślę o środkowych fragmentach.

Dobra robota Ants Aasma! Myślałem o odpowiedzi przez około 15 minut i samodzielnie wymyśliłem odpowiedź w podobnym tonie myślenia do twojego:

#define SWAP(x,y) { numerictype_t tmp = x; x = y; y = tmp; }
int minNonNegativeNotInArr (numerictype_t * a, size_t n) {
    int m = n;
    for (int i = 0; i < m;) {
        if (a[i] >= m || a[i] < i || a[i] == a[a[i]]) {
            m--;
            SWAP (a[i], a[m]);
            continue;
        }
        if (a[i] > i) {
            SWAP (a[i], a[a[i]]);
            continue;
        }
        i++;
    }
    return m;
}

m reprezentuje "bieżące maksymalne możliwe wyjście, biorąc pod uwagę to, co wiem o pierwszych wejściach i i nie zakładając nic więcej o wartościach aż do wejścia na m-1".

Ta wartość m zostanie zwrócona tylko wtedy, gdy (a [i], ..., a [m-1]) jest permutacją wartości (i, ..., m-1). Zatem jeśli a [i]> = m lub jeśli a [i] <i lub jeśli a [i] == a [a [i]] wiemy, że m to niewłaściwe wyjście i musi być co najmniej o jeden element niższe. Zatem zmniejszając m i zamieniając a [i] na a [m] możemy powtórzyć.

Jeśli to nie jest prawda, ale a [i]> i wtedy wiedząc, że a [i]! = A [a [i]] wiemy, że zamiana a [i] na a [a [i]] zwiększy liczbę elementów na swoim miejscu.

W przeciwnym razie a [i] musi być równe i, w którym to przypadku możemy inkrementować i, wiedząc, że wszystkie wartości do tego indeksu włącznie są równe ich indeksowi.

Dowód, że nie może to wejść w nieskończoną pętlę, pozostaje jako ćwiczenie dla czytelnika. :)

Dafny fragment z odpowiedziami pokazy mrówki dlaczego algorytm w miejscu może zakończyć się niepowodzeniem. requiresWarunek opisuje, że wartości poszczególnych pozycji nie może wykraczać poza granice tablicy.

method AntsAasma(A: array<int>) returns (M: int)
  requires A != null && forall N :: 0 <= N < A.Length ==> 0 <= A[N] < A.Length;
  modifies A; 
{
  // Pass 1, move every value to the position of its value
  var N := A.Length;
  var cursor := 0;
  while (cursor < N)
  {
    var target := A[cursor];
    while (0 <= target < N && target != A[target])
    {
        var new_target := A[target];
        A[target] := target;
        target := new_target;
    }
    cursor := cursor + 1;
  }

  // Pass 2, find first location where the index doesn't match the value
  cursor := 0;
  while (cursor < N)
  {
    if (A[cursor] != cursor)
    {
      return cursor;
    }
    cursor := cursor + 1;
  }
  return N;
}

Wklej kod do walidatora z forall ...klauzulą i bez niej , aby zobaczyć błąd weryfikacji. Drugi błąd jest wynikiem tego, że weryfikator nie jest w stanie ustalić warunku zakończenia pętli Pass 1. Udowodnienie tego należy do kogoś, kto lepiej rozumie narzędzie.

Oto odpowiedź w Javie, która nie modyfikuje danych wejściowych i używa czasu O (N) i N bitów oraz niewielkiego stałego narzutu pamięci (gdzie N to rozmiar listy):

int smallestMissingValue(List<Integer> values) {
    BitSet bitset = new BitSet(values.size() + 1);
    for (int i : values) {
        if (i >= 0 && i <= values.size()) {
            bitset.set(i);
        }
    }
    return bitset.nextClearBit(0);
}

def solution(A):

index = 0
target = []
A = [x for x in A if x >=0]

if len(A) ==0:
    return 1

maxi = max(A)
if maxi <= len(A):
    maxi = len(A)

target = ['X' for x in range(maxi+1)]
for number in A:
    target[number]= number

count = 1
while count < maxi+1:
    if target[count] == 'X':
        return count
    count +=1
return target[count-1] + 1

Otrzymałem 100% za powyższe rozwiązanie.

1) Filtruj negatyw i zero

2) Sortuj / wyraźne

3) Odwiedź tablicę

Złożoność : O (N) lub O (N * log (N))

używając Java8

public int solution(int[] A) {
            int result = 1;
    boolean found = false;
    A = Arrays.stream(A).filter(x -> x > 0).sorted().distinct().toArray();
    //System.out.println(Arrays.toString(A));
    for (int i = 0; i < A.length; i++) {
        result = i + 1;
        if (result != A[i]) {
            found = true;
            break;
        }
    }
    if (!found && result == A.length) {
        //result is larger than max element in array
        result++;
    }
    return result;
}

Unordered_set może służyć do przechowywania wszystkich liczb dodatnich, a następnie możemy iterować od 1 do długości unordered_set i zobaczyć pierwszą liczbę, która nie występuje.

int firstMissingPositive(vector<int>& nums) {

    unordered_set<int> fre;
    // storing each positive number in a hash.
    for(int i = 0; i < nums.size(); i +=1)
    {
        if(nums[i] > 0)
            fre.insert(nums[i]);
     }

    int i = 1;
    // Iterating from 1 to size of the set and checking 
    // for the occurrence of 'i'

    for(auto it = fre.begin(); it != fre.end(); ++it)
    {
        if(fre.find(i) == fre.end())
            return i;
        i +=1;
    }

    return i;
}

Rozwiązanie za pomocą podstawowego javascript

var a = [1, 3, 6, 4, 1, 2];

function findSmallest(a) {
var m = 0;
  for(i=1;i<=a.length;i++) {
    j=0;m=1;
    while(j < a.length) {
      if(i === a[j]) {
        m++;
      }
      j++;
    }
    if(m === 1) {
      return i;
    }
  }
}

console.log(findSmallest(a))

Mam nadzieję, że to pomoże komuś.

W przypadku Pythona nie jest to najbardziej wydajne, ale poprawne

#!/usr/bin/env python3
# -*- coding: UTF-8 -*-
import datetime

# write your code in Python 3.6

def solution(A):
    MIN = 0
    MAX = 1000000
    possible_results = range(MIN, MAX)

    for i in possible_results:
        next_value = (i + 1)
        if next_value not in A:
            return next_value
    return 1

test_case_0 = [2, 2, 2]
test_case_1 = [1, 3, 44, 55, 6, 0, 3, 8]
test_case_2 = [-1, -22]
test_case_3 = [x for x in range(-10000, 10000)]
test_case_4 = [x for x in range(0, 100)] + [x for x in range(102, 200)]
test_case_5 = [4, 5, 6]
print("---")
a = datetime.datetime.now()
print(solution(test_case_0))
print(solution(test_case_1))
print(solution(test_case_2))
print(solution(test_case_3))
print(solution(test_case_4))
print(solution(test_case_5))

def solution(A):
    A.sort()
    j = 1
    for i, elem in enumerate(A):
        if j < elem:
            break
        elif j == elem:
            j += 1
            continue
        else:
            continue
    return j

to może pomóc:

0- A is [5, 3, 2, 7];
1- Define B With Length = A.Length;                            (O(1))
2- initialize B Cells With 1;                                  (O(n))
3- For Each Item In A:
        if (B.Length <= item) then B[Item] = -1                (O(n))
4- The answer is smallest index in B such that B[index] != -1  (O(n))