Witam, Jak znaleźć najczęściej występujący element w tablicy jednowymiarowej?
Dokładnie, Mam tablicę typu int. Chcę znaleźć liczbę która występuje największą ilość razy.
Wiem że może być kilka takich liczb.
Ktoś ma pomysł na to?
0
2
Najwygodniej będzie posortować wszystkie liczby np. sortowaniem szybkim i przeiterować całą tablicę w poszukiwaniu identycznych liczb znajdujących się obok siebie.
Średnia złożoność takiego podejścia będzie wynosić O(n * log(n)), zamiast "prymitywnego" podejścia z dwoma pętlami, które dałoby O(n^2).
W specjalnym przypadku (np. nałożeniu ograniczenia na n będące (u)int8) można uzyskać O(n) poprzez podejście w stylu sortowania przez zliczanie.
0
Ok, jeśli posortuję, to jak dalej znaleźć liczby która występuje najczęściej? przecież nie będę wiedział ile razy ta liczba ma się tam pojawiać
1
Narysuj sobie na kartce taką posortowaną tablicę składającą się z 30 liczb i spróbuj znaleźć rozwiązanie.
0
myślę żeby najpierw przelecieć się pętlą po całej tablicy i znaleźć największą ilość wystąpienia, a później do drugiej tablicy przerzucić te elementy które taką ilość razy występują.