Strona główna » Algorytmy » Artykuły » Znajdowanie Lidera w zbiorze
 

Znajdowanie Lidera w zbiorze

https://mattomatti.com/a49

Wstęp

Załóżmy, że mamy listę L, która zawiera n elementów. Liderem zbioru nazwiemy element, który występuje więcej niż razy. Przykładowo jeśli mamy listę elementów liczb całkowitych L:={1, 2, 3, 4, 2, 2, 2} to liderem zbioru jest liczba 2, która występuje 4 razy i spełnia warunek 4 > 3.5. Jeśli usuniemy ostatni element to liczba 2 wystąpi tylko 3 razy i nie spełni warunku lidera, ponieważ nie jest prawdziwe, że 3 > 3.

Właściwości lidera

Algorytm, który napiszemy do wyszukiwania lidera wykorzysta pewną właściwość lidera. Jeśli usuniemy dwa różne elementy z listy L, która ma lidera to powstała lista L' też będzie miała lidera. Rozpatrzmy ponownie przykład listy L:={1, 2, 3, 4, 2, 2, 2}. Załóżmy, że usuniemy 1 i 3 - wtedy liczba 2 dalej pozostaje liderem. Nawet jeśli usuniemy element nielidera i element lidera to liczba dwa pozostanie liderem. Przykładowo usuwamy 1 i 2 z początku listy. Wtedy L':={3, 4, 2, 2, 2} i mamy 3 razy liczbę 2 i spełnia warunek 3 > 2.5.

Jednak takiej właściwości nie możemy przypisać zbiorom, które nie mają lidera. Przykładowo weźmy listę L:={1, 1, 2, 2, 3}. Lista L nie posiada lidera. Jednak po usunięciu 2 i 3 liderem listy L' zostaje liczba 1. Należy pamiętać, że wtedy z tego nie wynika, że lista L ma lidera (i tym bardziej, że jest to liczba 1).

Dowód poprawności

Przyjmijmy, że mamy listę L o długości n i lidera w zbiorze, który występuje a razy. Wtedy spełnia warunek 2a - n > 0. Teraz rozpatrzymy dwa przypadki: a) usuwamy dwa elementy nielidera oraz b) usuwamy jeden element nielidera i jeden lidera. Nie rozpatrujemy przypadku usunięcia dwóch wartości lidera, ponieważ wartości usuwanych elementów muszą być zgodnie z założeniem różne.

a) usuwamy dwa elementy nielidera czyli liczba wystąpień lidera a się nie zmienia, ale zmniejsza się długość listy n o dwa czyli: 2a - n + 2 > 0, ale korzystając z informacji, że a jest liderem to 2a - n > 0 praz 2 > 0, więc przypadek jest zawsze spełniony.

b) usuwamy element lidera i nielidera czyli liczba wystąpień lidera a się zmienia o 1. Długość listy n o dwa czyli: 2a - n > 0. Co jest zgodne ze wstępnymi założeniami, że a jest liderem.

Implementacja

Implementacja kodu wyznaczającego lidera opiera się na szczególnej właściwości lidera. Przeglądając wszystkie elementy będziemy na bieżąco wyznaczać aktualnego lidera. Na początek przyjmiemy, że pierwszy element jest liderem i przypiszemy pomocniczej zmiennej a wartość 1 co będzie oznaczać, że jest jedno wystąpienie lidera. Jeśli następny element jest aktualnym liderem to zwiększymy wartość a. Jednak jeśli nie jest to zmniejszymy. W momencie kiedy a = 0 to oznacza to, że do tej pory w podliście nie ma lidera. Następna iteracja przyjmie, o ile a = 0, że liderem jest i-ty element i rozpoczniemy poszukiwania od nowa. Ostatnim etapem algorytmu będzie sprawdzenie ile razy występuje lider.

Algorytm przeszuka całą listę dwa razy czyli uzyskamy złożoność liniową Θ(n).

  1. double znajdzLidera(const double* lista, const int n){
  2.   double lider = lista[0];
  3.   int wystapien = 1;
  4.   for(int i = 1; i < n; i++){
  5.     if (wystapien == 0){
  6.       lider = lista[i];
  7.       wystapien = 1;
  8.     } else {
  9.       wystapien += (lista[i] == lider) ? 1 : -1;
  10.     }
  11.   }

(1.) Funkcja przyjmuje dwa argumenty: lista - lista elementów (tutaj lista liczb rzeczywistych) oraz n rozmiar lista. Zwracanym typem jest liczba rzeczywista - element z lista. Jednak w przypadku, gdy lidera nie będzie to zostanie zwrócona wartość NULL. (2.) Przyjmujemy, że pierwszy element na liście jest liderem. (3.) Zapamiętujemy, że do tej pory wystąpił raz. (4.) Dla każdego elementu na liście począwszy od drugiego: (5.) sprawdzamy czy liczba wystąpień jest równa 0. Jeśli tak jest to zaczynamy poszukiwania lidera od początku czyli: (6.) przyjmujemy za lidera i-ty element i (7.) zaznaczamy, że wystąpił tylko raz. (9.) Jednak jeśli nie to (9.) porównujemy i-tego z aktualnym liderem. Jeśli są takie same to zwiększamy ilość wystąpień o jeden. W przeciwnym przypadku zmniejszamy o jeden.

  1.   if(wystapien == 0){
  2.     return NULL;
  3.   } else {
  4.     wystapien = 0;
  5.     for(int i = 0; i < n; i++){
  6.       if (lista[i] == lider)
  7.         wystapien++;
  8.     }
  9.     return (wystapien > n/2) ? lider : NULL;
  10.   }
  11. }

(12.) W przypadku listy parzystej brak obecności lidera możemy określić po ostatecznej różnicy zmiennej wystapien. Jeśli wystapien = 0 to oznacza to, że zachodzi równowaga na liście. (13.) Wtedy zwracamy wartość NULL. Jednak, żeby potwierdzić lidera to musimy policzyć ilość jego wystąpień: (15.) Zmienną wystapien ustawiamy na 0 - od tej pory będzie zliczać ilość wystąpień lidera. (16.) Przeglądamy każdy element na liście i (17.) jeśli i-ty jest równy lider to (18.) zwiększamy ilość wystąpień przechowywanych w wystapien. Na koniec (20.) sprawdzamy warunek: w przypadku spełnienia zwracamy lider. W przeciwnym NULL.

Testowanie funkcji

Poniższa funkcja main() poprosi użytkownika o wprowadzenie liczby n tj. ile elementów ma lista, a potem funkcja wczyta n rzeczywistych liczb. Potem program wypisze na konsole lidera o ile taka wartość istnieje.

  1. int main () {
  2.   int n;
  3.   cin >> n;
  4.   double* L = new double[n];
  5.   for(int i = 0; i < n; i++)
  6.     cin >> L[i];
  7.   double lider = znajdzLidera(L, n);
  8.   if(lider == NULL){
  9.     cout << "lista nie ma lidera" << endl;
  10.   } else {
  11.     cout << "liderem jest " << lider << endl;
  12.   }
  13.   delete[] L;
  14.   system("pause");
  15.   return 0;
  16. }

(7.) Zwrócony wynik zapisujemy w zmiennej lider i (8.) odpowiednio go interpretujemy.

Zadania

Zadanie 1

Napisz funkcję, która wczyta uporządkowaną listę (nie trzeba tego sprawdzać) liczb całkowitych i wyznaczy jej lidera. Znajdź sposób, aby funkcja przejrzała wszystkie elementy listy dokładnie raz.

Przykładowo dla listy {5, 1, 1, 1, 2, 2} na ekran zostanie wypisane:

  1. 1