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
0
Pytasz raczej o zagadnienie algorytmiczne.
Podpowiedź: Taka liczba, będzie nie większa niż liczba elementów w zbiorze.
2
- Wrzucamy liczby do hashseta (czas O(n) * O(1) = O(n)) -> https://en.cppreference.com/w/cpp/container/unordered_set
- Lecimy po liczbach 0..n i szukamy pierwszej której nie ma w secie (O(n) * O(1) = O(n))