Lider w zbiorze

Czym jest lider? Określamy tak liczbę, która występuje w zbiorze n-elementowym więcej niż $\frac{n}{2}$ razy. Ponieważ dwie różne liczby nie mogą występować w tym samym zbiorze liczbowym więcej niż $\frac{n}{2}$ razy, lider jest tylko jeden.

Na przykład w zbiorze {1, 4, 6, 1, 1} lider to liczba 1, ponieważ występuje w nim aż 3 razy.

$\frac{n}{2}=\frac{5}{2}=2,5\iff 3>2,5$

Natomiast w zbiorze {8, 6, 4, 5, 2, 2} żadna z sześciu liczb nie jest liderem, choć liczba 2 występuje więcej razy niż pozostałe.

Zbiory, które mają lidera, posiadają bardzo ważną właściwość: jeżeli z takiego zbioru usuniemy parę różnych liczb, zbiór ten nadal będzie miał tego samego lidera.

Rozważmy dwa przypadki.

Pierwszy dotyczy usunięcia pary liczb, z której żadna nie jest liderem. Ze zbioru {1, 4, 6, 1, 1} usuwamy liczby 4 oraz 6 i zostajemy z podzbiorem {1, 1, 1}. Ponieważ zbiór ten składa się tylko z jedynek, bardzo łatwo stwierdzić, że lider tego zbioru nie zmienił się i nadal jest nim liczba 1.

W drugim przypadku usuniemy jedną liczbę, która nie jest liderem, i jedną, która nim jest – czyli usuniemy liczby 4 oraz 1. Zostajemy wtedy ze zbiorem {1, 6, 1}, którego liderem nadal jest liczba 1. Ponieważ para, która zostaje wyeliminowana, nie może składać się z tych samych liczb, przypadek, w którym usunięte zostaną dwie liczby lidera, nie zaistnieje.

Algorytm wyboru lidera

Specyfikacja problemu:

Dane:

• n – liczba naturalna; liczba elementów zbioru zbiór

• zbior – zbiór liczb naturalnych

Wynik:

• komunikat wskazujący lidera zbioru lub informujący, że zbiór nie ma lidera

Przykład będzie bazował na zbiorze trzyelementowym, ponieważ łatwiej będzie na nim wskazać pewne zależności.

Wykorzystamy poznaną zależność.

Załóżmy, że pierwsza liczba ze zbioru jest liderem, oraz stwórzmy zmienną, która będzie liczyć wystąpienia lidera. Nazwijmy ją licznik. Skoro zakładamy, że pierwsza liczba jest liderem, zmienną licznik inicjalizujemy wartością 1, ponieważ jedno wystąpienie potencjalnego lidera już nastąpiło. Dodajemy również zmienną, która będzie przechowywała liczbę elementów zbioru.

W pseudokodzie będzie to wyglądało następująco:

zbior ← {1, 3, 1}
lider ← zbior[0]
licznik ← 1
n ← 3

Następnym krokiem będzie iteracja przez cały zbiór. Ponieważ zakładamy, że pierwszy element zbioru jest liderem, i został on już uwzględniony w zmiennej licznik, możemy go pominąć w pętli i zainicjować zmienną sterującą wartością 1.

zbior ← {1, 3, 1}
lider ← zbior[0]
licznik ← 1
n ← 3

dla i = 1, 2,... n - 1 wykonuj
   

Naszym celem jest eliminacja par liczb, które nie są takie same. W konsekwencji, jeżeli kolejny element zbioru nie jest taki sam jak dotychczasowy lider (czyli poprzedni element), zmniejszymy wartość zmiennej licznik o jeden. W kolejnej iteracji sprawdzimy, czy zmienna licznik ma wartość 0. Jeżeli warunek jest prawdziwy, przesuniemy lidera na miejsce sprawdzanego elementu, ponieważ oznacza to, że para, która została sprawdzona, zawierała dwie różne liczby – może zatem zostać pominięta. Zobaczmy, jak będzie to wyglądać w pseudokodzie, a następnie przetestujmy działanie tej części algorytmu na przykładzie:

zbior ← {1, 3, 1}
lider ← zbior[0]
licznik ← 1
n ← 3

dla i = 1, 2,... n - 1 wykonuj
	jeżeli licznik > 0 to
		jeżeli lider ← zbior[i] to
			licznik ← licznik + 1
		w przeciwnym wypadku
			licznik ← licznik - 1
	w przeciwnym wypadku
		lider ← zbior[i]
		licznik ← 1

Dla przykładu rozważmy zbiór {1, 3, 1, 3, 1, 3, 1}, w którym liderem jest 1, i przeanalizujmy działanie algorytmu.

zbior ← {1, 3, 1, 3, 1, 3, 1}
lider ← 1
licznik ← 1
n ← 3

Wchodzimy w pętlę for, zmienna sterująca i otrzymuje wartość 1. Zmienna licznik ma wartość 1, więc jest większa niż 0.

Czy lider jest równy zbior[i]? Podstawmy wartości i sprawdźmy.

Po podstawieniu wartości wiemy, że wartości tych zmiennych nie są sobie równe.

Odejmujemy od zmiennej sterującej 1 i przechodzimy do kolejnej iteracji. Zmienna licznik jest równa 0, więc przenosimy lidera do zbior[2] czyli 1, a zmiennej licznik przypisujemy wartość 1. Dzięki temu pierwsza para (1, 3) zostaje usunięta, ponieważ liczby w tej parze nie są takie same.

Co się jednak dzieje, gdy para zawiera te same liczby? Ponieważ liczba powtórzyła się, zostaje kandydatem na lidera. Zwiększamy więc wartość zmiennej licznik, która liczy liczbę wystąpień potencjalnego lidera.

W rezultacie działania pętli otrzymamy potencjalnego lidera oraz zmienną licznik. Jeżeli wartość zmiennej licznik wynosi 0, badany zbiór nie ma lidera. Aby mieć pewność, że potencjalny lider jest faktycznie liderem, policzymy liczbę jego wystąpień w zbiorze i sprawdzimy, czy liczba ta jest większa niż długość zbioru podzielona na 2. Dodajmy te zmiany do algorytmu:

zbior ← {1, 3, 1}
lider ← zbior[0]
licznik ← 1
n ← 3

dla i = 1, 2,...n - 1 wykonuj
	jeżeli licznik > 0 to
		jeżeli lider = zbior[i] to
			licznik ← licznik + 1
		w przeciwnym wypadku
			licznik ← licznik - 1
	w przeciwnym wypadku
		lider ← zbior[i]
		licznik ← 1

jeżeli licznik = 0 to
	wypisz "Zbiór nie ma lidera"
	zakończ działanie programu
  
liczba_wystapien_lidera ← 0
dla i = 0, 1,...n - 1 wykonuj
	jeżeli zbior[i] = lider to
		liczba_wystapien_lidera = liczba_wystapien_lidera + 1
    
jeżeli liczba_wystapien_lidera > n / 2 to
	wypisz "Liderem zbioru jest " + lider
w przeciwnym wypadku
	wypisz "Zbiór nie ma lidera"

Dominującymi operacjami w omawianym rozwiązaniu są porównania w pętlach wykonujących się dla każdego elementu zbioru wejściowego, a zatem złożoność czasowa algorytmu wynosi $O\left(n\right)$.

Implementacja w języku Python

zbior = [1, 3, 1]
lider = zbior[0]
n = 1

for i in range(1,len(zbior)):
	if n > 0:
		if lider == zbior[i]:
			n = n + 1
		else:
			n = n - 1
	else:
		lider = zbior[i]
		n = 1
		
if n == 0:
	print("Zbiór nie ma lidera")
	exit()
    
liczba_wystapien_lidera = 0
for i in  range(0,len(zbior)):
	if zbior[i] == lider:
		liczba_wystapien_lidera += 1
    
if liczba_wystapien_lidera > len(zbior) / 2:
    print("Liderem zbioru jest ",lider)
else:
	print("Zbiór nie ma lidera")