Witam, mam do zrobienia algorytm, który ma wyznaczać dominantę i medianę z tablicy jednowymiarowej. Miałby ktoś dla mnie jakieś wskazówki? Dodam że muszę to wykonać w scilabie.
0
1
Jak Masz posortowaną tablice, to mediana nie jest problemem; a dominanta, tutaj:
https://www.tutorialspoint.com/learn_c_by_examples/mode_program_in_c.htm#
jest pseudokod i kod w C
, przepisanie nie powinno być problemem.
2
Jak masz posortowaną tablicę to:
- Mediana to po prostu środkowy element tej tablicy ->
tablica[len(tablica)/2]
ewentualnie +-1 w zależności od tego co masz zwrócić dla parzystej liczby elementów w tablicy - Dominanta to element który występuje najczęściej. Lecisz sobie po liczbach i podbijasz licznik dopóki są takie same. Jeśli wyszło ci więcej niż aktualny max (początkowo 0) to zmieniasz maxa i zapamiętujesz dla jakiej liczby go miałeś. Potem dalej lecisz po kolejnych liczbach.
Dominante można zrobić bez sortowania w O(n)
zamiast O(nlogn)
, wystarczy zrobić zliczanie z jakąś hashmapą.
Medianę też można bez sortowania, algorytmem magicznych piątek / mediana median i też dostaniesz O(n)
zamiast O(nlogn)