: index | programowanie | webmastering | algorytmika | download | projekty | słownik | grafika | flash | linki :

a l g o r y t m y > działania na liczbach >

W Y S Z U K I W A N I E   L I D E R A

 

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 29 30

 
       

Liderem n-elementowego ciągu nazywamy element występujący w tym ciągu więcej niż [n Div 2] razy. Tak samo można określić lidera w zbiorze, choć trzeba przyznać, że kłóci się to z intuicjami dotyczącymi zbioru, które sugerują, że zbiór nie zawiera takich samych elementów.

Jeśli ciąg posortujemy w porządku rosnącym lub malejącym, to lider, o ile występuje, będzie elementem mniej więcej środkowym tego ciągu: dla n parzystego powinien to być element a[n Div 2], dla n nieparzystego element a[n Div 2] lub a[(n Div 2)+1].
Efektywne sortowanie zajmuje czas O(n*log(n)), sprawdzenie czy liczba środkowa jest liderem czas n - łącznie da to złożoność rzędu O(n*log(n)).

Algorytm szybszy o małej złożoności O(n), ale wymagąjący dodatkowej tablicy o rozmiarze równym zakresowi elementów ciągu polega na przeglądnięciu wszystkich elementów ciągu i zliczeniu ilośći wystąpień każdego elementu występującego w ciągu:

For i:=1 To n Do c[a[i]]:=c[a[i]]+1;

i sprawdzeniu czy liczba największa w tablicy c jest większa od n Div 2.

Algorytm nie wymagający dodatkowej tablicy polega na przeglądnieciu wszystkich kolejnych sąsiadujących ze sobą par elementów. Wstępnie przyjmujemy, że liderem ciągu jest wyraz a[1], ilość jego wystąpień ile w ciągu ustalamy na 1. Jeśli w parze sąsiednich elementów a[i-1]=a[i], to zwiększamy o 1 ilość wystąpień lidera, jeśli wyrazy są różne, to:

  • wykonamy zmniejszenie ile:=ile-1, gdy ile>1,

  • zmienimy kandydata na lidera, gdy ile=1.

lider:=a[1];
ile:=1;
For i:=2 To n Do
  If a[i-1]=a[i] Then ile:=ile+1
   Else
     If ile>1 Then ile:=ile-1
     Else lider:=a[i];

Po zakończeniu tej pętli jeśli ciąg zawiera lidera, to jest nim wyraz równy lider.
Złożoność obliczeniowa: O(n).