wyszukiwanie lidera w zbiorze

Problem

W n-elementowym zbiorze Z znaleźć element, którego wartość występuje więcej niż ⁿ/₂ razy.

Element o takich własnościach nosi nazwę lidera. Lidera można znaleźć przy pomocy jednego z opisanych w poprzednim rozdziale algorytmów wyszukiwania najczęstszej wartości w zbiorze. Po znalezieniu takiej wartości sprawdzamy, czy liczba jej wystąpień jest większa od liczby połowy elementów zbioru Z. Jeśli tak, to mamy lidera. Jeśli nie, to zbiór Z nie posiada lidera.

Istnieje jednakże prostszy i szybszy algorytm, który korzysta z następującego twierdzenia:

Jeśli zbiór Z posiada lidera, to usunięcie z niego pary elementów różnych daje zbiór z tym samym liderem.

Dowód tego twierdzenia jest bardzo prosty. Oznaczmy przez n_L liczbę elementów będących liderami. Zbiór Z posiada n elementów, zatem liczba pozostałych elementów wynosi n - n_L. Zachodzi nierówność:

n_L > n - n_L

Przypadek 1

Ze zbioru Z usuwamy dwa elementy, które nie są liderami. W tym przypadku n_L nie zmniejsza się, lecz zmniejsza się o 2 liczba elementów n. Otrzymamy zatem:

n_L > (n - 2) - n_L
n_L > (n - n_L) - 2

Jeśli pierwsza nierówność była prawdziwa (a była z założenia, iż n_L jest liczebnością liderów), to tym bardziej będzie prawdziwa druga nierówność. Wynika z tego, iż usunięcie dwóch elementów nie będących liderami nie wpływa na występowanie lidera.

Przypadek 2

Ze zbioru Z usuwamy jeden element lidera oraz jeden element nie będący liderem. Zmniejszeniu o 1 ulega zatem liczba liderów, a liczba elementów maleje o 2. Otrzymujemy:

n_L - 1 > (n - 2) - (n_L - 1)
n_L - 1 > n - 2 - n_L + 1
n_L - 1 > (n - n_L) - 1

Otrzymaliśmy nierówność wyjściową, w której od obu stron odjęto tę samą liczbę -1. Zatem nierówność jest wciąż prawdziwa, z czego wynika, iż usunięcie ze zbioru jednego lidera i jeden element nie będący liderem nie wpływa na występowanie lidera.

Innych przypadków nie ma, zatem dowiedliśmy prawdziwości twierdzenia.

Z powyższego twierdzenia bezpośrednio wynikają dwie dalsze własności:

Jeśli zbiór posiada lidera, to usunięcie z niego wszystkich par elementów różnych daje zbiór zawierający tylko elementy będące liderem.Jeśli w wyniku takiej operacji otrzymujemy jednak zbiór pusty, to lidera w zbiorze wejściowym nie było.

Zamiast faktycznie wyrzucać ze zbioru elementy różne – co jest dosyć trudne, możemy wykonać operację odwrotną. Będziemy zliczali elementy o równych wartościach – wystarczy wtedy zapamiętać wartość elementu oraz ilość jej wystąpień. Algorytm pracuje w sposób następujący:

Licznik elementów równych L ustawiamy na zero. Rozpoczynamy przeglądanie elementów zbioru od pierwszego do ostatniego. Jeśli licznik elementów równych L jest równy 0, to kolejny element zbioru zapamiętujemy, zwiększamy licznik L o 1 i wykonujemy kolejny obieg pętli dla następnego elementu. Jeśli licznik L nie jest równy zero, to sprawdzamy, czy bieżący element jest równy zapamiętanemu. Jeśli tak, to mamy dwa elementy równe – zwiększamy licznik L o 1. W przeciwnym razie licznik L zmniejszamy o 1 – odpowiada to wyrzuceniu ze zbioru dwóch elementów różnych. W obu przypadkach wykonujemy kolejny obieg pętli.

Jeśli zbiór posiadał lidera, to liczba elementów równych jest większa od liczby elementów różnych. Zatem licznik L powinien mieć zawartość większą od zera. Jeśli zawartość licznika L jest równa zero, to lidera w zbiorze nie ma. W przeciwnym razie zapamiętany element należy przeliczyć w zbiorze – jest to kandydat na lidera. Jeśli liczba jego wystąpień jest większa od liczby połowy elementów, to wytypowany element jest liderem. W przeciwnym razie zbiór Z nie posiada lidera.

Algorytm posiada liniową klasę złożoności obliczeniowej O(n), jest zatem bardziej efektywny od opisanych w poprzednim rozdziale algorytmów wyszukiwania najczęstszej wartości.

Program

Program umieszcza w tablicy Z 80 liczb pseudolosowych z zakresu od 0 do 99 w taki sposób, aby mógł się pojawić w niej lider. Następnie program wyszukuje lidera podanym powyżej algorytmem, wyświetla zawartość tablicy z zaznaczonym liderem  i wypisuje jego wartość oraz liczbę wystąpień. Jeśli pomimo wszystko zdarzy się, iż w tablicy Z nie będzie lidera, program wypisze tekst BRAK LIDERA.