Jak znaleźć najmniejszą liczbę niewystępującą we zbiorze w czasie liniowym

0

Mamy na wejściu dany n-elementowy zbiór liczb, w którym wszystkie liczby są różne np.
1 4 2 5 7 9 0, liczby są od 0 do 10^18. Jak znaleźć najmniejszą liczbę niewystępującą w tym zbiorze w złożoności liniowej?

0

Pytasz raczej o zagadnienie algorytmiczne.
Podpowiedź: Taka liczba, będzie nie większa niż liczba elementów w zbiorze.

2
  1. Wrzucamy liczby do hashseta (czas O(n) * O(1) = O(n)) -> https://en.cppreference.com/w/cpp/container/unordered_set
  2. Lecimy po liczbach 0..n i szukamy pierwszej której nie ma w secie (O(n) * O(1) = O(n))

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0