Lider w zbiorze

Znajdowanie lidera w zbiorze

powrót

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.

Rozwiązanie w C++:

#include<iostream> #include<cstdlib> using namespace std;   int szukaj_lidera(int tab[],int n) { int lider = tab[0], do_pary = 1;   //wykreślanie par o różnych wartościach for(int i=1;i<n;i++) if(do_pary > 0) if(tab[i]==lider) ++do_pary; else --do_pary; else { ++do_pary; lider = tab[i]; } //koniec wykreślania   if(do_pary==0) return -1; //zwrócenie -1 oznacza, że zbiór nie posiada lidera   int ile = 0; //zmienna zliczająca wystąpieńia potencjalnego lidera   for(int i=0;i<n;i++) //zliczamy wystąpienia lidera if(tab[i]==lider) ++ile;   if(ile>n/2) //sprawdzamy, czy potencjalny lider występuje oczekiwaną ilość razy return lider;   return -1; }   int main() { int n, *tab, lider;   cout<<"Ile liczb chcesz wczytać? "; cin>>n;   tab = new int [n];   for(int i=0;i<n;i++) cin>>tab[i];   lider = szukaj_lidera(tab,n);   if(lider==-1) cout<<"Zbiór nie posiada lidera"<<endl; else cout<<"Liderem zbioru jest "<<lider<<endl;   delete [] tab;   return 0; }