Jest ciąg o rozmiarze n i trzeba wyznaczyć jaka liczba się powtarza najczęściej i ile razy (przykład: jest ciąg 9, 1, 2, 3, 4, 5, 4. Najczęściej powtarza się liczba '4', 2 razy). Bardzo proszę o podawanie jak najszybszych rozwiązań w C++.
0
1
A jaki jest zakres tych liczb? Jak mały to użyj zwykłego zliczania
for liczba in ciąg:
conter[liczba]++;
A jak liczby mogą być bardzo duże, to to samo, ale z użyciem hashmapy
1
Najszybsze będzie zliczanie do mapy – dla std::unordered_map (hashmapa), która ma średni koszt wstawiania O(1), ostatecznie będzie O(n):
- Skanowanie wejścia + wstawianie: O(n * O(1)) = O(n) (średnio)
- Znalezienie maksymalnej wartości w hashmapie: O(n)
W sumie czas liniowy.