Moda jest to wartość ze zbioru, która najczęściej występuje. Takich elementów może być więcej niż jeden i wtedy wszystkie takie wartości nazywa się dominantami. W tym artykule zostanie wyjaśnione jak zaimplementować algorytm do wyszukiwania dominant.
W celu znalezienia dominanty należy policzyć ile razy występuje, który element, a następnie sprawdzić, które pary element×liczba wystąpień ma największą liczbę wystąpień. Podczas formułowania odpowiedzi należy pamiętać, że może być kilka dominant tj. elementów, które występują najczęściej.
Weźmy przykładowo zbiór {1, 3, 5, 2, 4, 3, 1, 5, 5}. Dla podanego zbioru liczb utwórzmy tablicę, gdzie dla każdej wartości policzymy ile razy występuje. Dane zostały zebrane w tabelce:
| Wartość | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Wystąpień | 2 | 1 | 2 | 1 | 3 |
Z tabelki wyraźnie wynika, że najczęściej występuje wartość 5, a więc jest to dominanta tego zbioru. Jednak gdyby w zbiorze nie istniała wartość 5 to dominantami byłyby wartości 1 oraz 3.
Do przechowywania par wartość oraz ilość wystąpień warto napisać własną strukturę, albo skorzystać z dwuelementowych krotek. Wszystkie takie pary powinny być odkładane na specjalną listę. Elementy na niej umieszczone powinny zostać posortowane w trakcie wstawiania - dzięki temu do wyszukania czy dana wartość została już znaleziona wystarczy logn kroków, a nie n. Jest to możliwe dzięki wykorzystaniu wyszukiwaniu binarnemu.
Na koniec pozostaje przeanalizować utworzoną listę tak, aby można było określić, które wartości są dominantami, a które nie. W tym celu zostanie utworzona pusta lista, a maksymalna ilość wystąpień ustawiona na 0. Nastepnie przeszukując po kolei pary jeśli liczba wystąpień jest taka sama jak aktualne maksimum to wartość należy dopisać, a jeśli większa to lista jest czyszczona, maksimum ustawiane na ilość wystapień danej wartości, a następnie dopisywana na listę jest aktualna wartość.
Złożoność pamięciowa jest liniowa O(n), a złożoność czasowa to O(n·logn). Wynika to z faktu, że dla każdego z n elementów wykonujemy wyszukiwanie binarne o złożności O(logn), a następnie wykonujemy przejście po całej tablicy o maksymalnej długości n jeśli każda wartosć występuje raz, więc O(n·logn + n) = O(n·logn).
Przykładowo dla zbioru {1, 3, 2, 3, 2, 3, 1} zostaną otrzymane następujące pary:
| Wartość | 1 | 2 | 3 |
|---|---|---|---|
| Wystąpień | 2 | 2 | 3 |
Z kolei wyszukiwanie dominant odbędzie się w następujący sposób:
| Wynik | Maksimum | Wartość | Wystąpień | Komentarz |
|---|---|---|---|---|
| [] | 0 | 1 | 2 | Liczba wystąpień 1 jest większa od maksimum, więc lista jest czyszczona, a 1 zostaje dopisane |
| [1] | 2 | 2 | 2 | Liczba wystapień 2 jest taka sama jak maksimum, więc dopisujemy dwa na listę |
| [1, 2] | 2 | 3 | 3 | Liczba wystąpień 3 jest większa niż maksimum, więc lista jest czyszczona, a 3 zostaje dopisane |
| [3] | 3 | - | - | - |
Na podstawie uzyskanego wyniku można stwierdzić, że istnieje tylko jedna dominanta tj. 3.
Poniższa funkcja szukajDominanty() dla podanej tablicy dane zwraca listę dominant.
(2.) Przygotuj nową listę, a następnie (3.) umieść na liście pierwszy element z listy wejściowej. Następnie (4.) dla każdego elementu: (5.) znajdź gdzie powinna znajdować się para wartości odpowiadająca elementowi. (6.) Jeśli na tej pozycji występuja para z szukaną wartością to (7.) zwiększ ilość. (8.) W przeciwnym razie (9.) dodaj nową parę na znalezionej pozycji. Dzięki temu mamy pewność, że lista jest posortowana i można korzystać z wyszukiwania binarnego. Drugi etap polega na (10.) przypisaniu, że najczęstsza wartość wystąpiła zero razy, a lista wynikowa jest pusta. (11.) Dla każdej pary: (12.) jeśli występuje częściej niż aktualne maksimum to (13.) oczyść listę i (14.) ustal nowe maksimum. Niezależnie od poprzedniego warunku (15.) sprawdź czy ilość wystąpień jest równa maksimum i jeśli tak to (16.) dopisz element na koniec. Po tej procedurze (17.) warto usunąć zbędne pary i (18.) zwrócić wynik.
Z kolei funkcja wyszukaj() to modyfikacja wyszukiwania binarnego. Nie zwraca ona informacji czy dana wartość wystepuje wśród par, a pozycję na której ta wartość powinna wystąpić. Dokładny opis wyszukiwania binarnego można znaleźć tutaj.
W celu przetestowania kodu można skorzystać z poniższego fragmentu kodu:
Wyszukiwanie dominanty można też zrealizować poprzez posortowanie danych, a następnie liniowo sprawdzeniu wszystkich elementów i wykrycia grup, które mają największą liczbę elementów. Przykładowo dla tablicy {1, 3, 2, 3, 2, 3, 1} wpierw zostanie posortowana jako {1, 1, 2, 2, 3, 3, 3}, a potem zostaną policzone kolejne grupy elementów o tym samych wartościach. Napisz funkcję szukajDominantaSort(), aby znaleźć dominantę (dominanty). Przetestuj działanie progrmau.