Wyszukiwanie lidera w zbiorze liczbowym

Wyszukiwanie lidera w zbiorze liczbowym 

Lider to taka wartość w zbiorze elementów, która powtarza się więcej niż razy. Jeśli istnieje taka wartość, to jest ona tylko jedna. Prześledźmy przykłady:
ciąg liczb

nie posiada lidera, ponieważ żadna z liczb nie wystąpiła co najmniej razy.

Ciąg

także nie posiada lidera, natomiast dla  liczb

liderem jest liczba .

Strategia jest następująca. Przeszukujemy liniowo kolejne elementy i w danym etapie dwa różne elementy zbioru wykreślamy - tak jak by ich nie było. Jeśli lider występuje w zbiorze, to jego "pozycja" w otrzymanym podzbiorze się nie zmieni. Przeanalizujmy następujący przykład:

i pozostał na zbiór, w którym nadal mamy lidera:

Redukując w ten sposób elementy dochodzimy do sytuacji, gdy pozostanie element, który jest kandydatem na lidera. Musimy teraz tylko liniowo zliczyć i sprawdzić, czy dana wartość występuje więcej niż razy.

Warto podkreślić, że znaleziony element nie musi być liderem. Prześledźmy przykład, w którym nie ma lidera:

Po wykreśleniu dwóch początkowych wyrazów pozostaje podzbiór

,

w którym jest lider.

W programie przedstawionym poniżej ważną rolę odgrywa zmienna . Odpowiedzialna jest ona za kontrolowanie wykreślania dwóch elementów o różnych wartościach. Jeśli wykreślimy wszystkie elementy, oznacza to, że żadna wartość nie spełnia oczekiwań. Przeanalizujmy przypadek:

W przypadku znalezienia liczby różnej od aktualnego lidera, wykreślamy ją zmniejszając wartość zmiennej . Gdy znajdziemy taką samą, wartość zmiennej inkrementujemy. Jeśli  będzie liczbą większą od zera, oznacza to, że zmienna przechowuje potencjalnego lidera zbioru.