Element większości z C ++

Niech n będzie liczbą elementów w wektorze lub tablicy. Element lub lider większości jest elementem, który występuje ponad połowę razy wszystkich elementów w wektorze. Połowa n oznacza: jeśli n wynosi 10, to połowa czasu to 5. Element w połowie pozycji jest w indeksie 4, dla liczenia indeksu opartego na zero. Najmniej liczba całkowita, która wynosi ponad połowę 10, jest wyraźnie 6 (odpowiadająca wskaźnikowi 5). Jeśli n wynosi 11, wówczas połowa n jest nadal uważana za 5. To jest liczba całkowitą pobrana, gdy 11 jest podzielona przez 2. Indeks dla połowy wynosi 4 dla indeksowania opartych na zero. Gdy n wynosi 11, najmniej liczba całkowita, która jest wyraźnie większa niż literalna połowa 11, jest nadal 6 (odpowiadająca wskaźnikowi 5).

Tak więc połowa długości (wielkości) wektora jest wynikiem podziału liczb całkowitych n przez 2. Oznacza to, że liczba ilorazu, po podzieleniu przez 2, jest przyjmowana, czy jest pozostała część.

Element lub lider większości jest elementem, który występuje ponad połowę razy wszystkich elementów w wektorze lub tablicy. To musi być więcej niż połowa razy, a nie tylko połowa razy. Oznacza to, że musi to być więcej niż N/2 razy (biorąc wynikową liczbę całkowitą). Funkcja powinna zwrócić -1, jeśli nie ma większości elementu.

W tym artykule wyjaśniono, jak określić element większości dla złożoności czasu O (n). To znaczy maksymalnie n głównych operacji, aby uzyskać element większości.

Przykłady wektorowe

Rozważ następujący wektor:

wektor A = 6, 8, 4, 6, 8, 6, 6

Element większości (lider) to 6. Występuje 4 razy na 7 razy (elementy).

Rozważ następujący wektor:

wektor B = 3, 4, 3, 2, 3, -1, 3, 3

Element większości to 3. Występuje 5 razy na 8 elementów.

Rozważ następujący wektor:

wektor C = 4, 3, 4, 4, 4, 2

Element większości to 4. Występuje 4 razy z 6 elementów.

Rozważ następujący wektor:

wektor D = 5, 4, 7, 1, 7, 2, 3, 7, 8

Nie ma tu większościowego elementu. Tak więc funkcja musi zwrócić -1. Tutaj jest dziewięć elementów. Liczba, 7, występuje trzy razy, a każdy z pozostałych elementów występuje raz. Trzy to nie więcej niż połowa dziewięciu. Powinien był wystąpić dopuszczalny element większościowy, co najmniej 5 razy.

Ilustracja algorytmu dla złożoności czasowej O (n)

Z następujących wektorów dwa różne elementy są usuwane jednocześnie.

Rozważ ponownie wektor:

wektor A = 6, 8, 4, 6, 8, 6, 6

Element lidera (większości) to 6. Pierwsze dwa elementy są różne. Jeśli oba zostaną usunięte, pozostały zestaw byłby, 4, 6, 8, 6, 6. W tym pozostałym zestawie 6 jest nadal liderem: trzy razy na 5 razy. Następne dwa elementy, 4 i 6 są różne. Jeśli zostaną usunięte, pozostały zestaw będzie 8, 6, 6. W pozostałym zestawie 6 jest nadal liderem. Następne dwa elementy, 8 i 6 są różne. Jeśli zostaną usunięte, pozostały zestaw będzie 6. W ostatnim zestawie tylko jednego elementu 6 jest nadal liderem. Wygląda zatem, jakby dwie różne liczby są usuwane wielokrotnie. Ostatni pozostały element byłby elementem większościowym.

Rozważ teraz wektor:

wektor B = 3, 4, 3, 2, 3, -1, 3, 3

Element lidera (większości) to 3. Pierwsze dwa elementy są różne. Jeśli oba zostaną usunięte, pozostały zestaw byłby, 3, 2, 3, -1, 3, 3. W tym pozostałym zestawie 3 nadal jest liderem: cztery razy na sześć razy. Następne dwa elementy, 3 i 2 są różne. Jeśli zostaną usunięte, pozostały zestaw będzie 3, -1, 3, 3. W pozostałym zestawie 3 nadal jest liderem. Następne dwa elementy, 3 i -1 są różne. Jeśli zostaną usunięte, pozostały zestaw wyniesie 3, 3. W ostatnim zestawie dwóch elementów 3 nadal jest liderem. Dlatego nadal wygląda na to, że dwie różne liczby są usuwane wielokrotnie. Ostateczne same pozostałe elementy byłyby elementem większościowym.

Rozważ następny wektor:

wektor C = 4, 3, 4, 4, 4, 2

Element lidera (większości) to 4. Pierwsze dwa elementy są różne. Jeśli oba zostaną usunięte, pozostały zestaw byłby, 4, 4, 4, 2. W tym pozostałym zestawie 4 nadal jest liderem: trzy razy na cztery razy. Następne dwa elementy, 4 i 4 są takie same i nie należy ich usuwać. Jednak pierwszy element tutaj i trzeci element tutaj można rozważyć do usuwania. Zdarza się, że te dwa są również takie same. Mimo to pierwszy element i czwarty element można rozważyć do usuwania. Są różne, więc są usuwane. Pozostały ostatni zestaw to 4, 4. Dlatego nadal wygląda na to, że dwie różne liczby są usuwane wielokrotnie. Ostateczne pozostałe same elementy byłyby elementem większości.

Rozważ wtedy wektor:

wektor D = 5, 4, 7, 1, 7, 2, 3, 7, 8

Wiemy już, że ten wektor nie ma lidera, choć 7 występuje trzy razy, a liczba nawzajem występuje raz. 7 występuje trzy na dziewięć razy, a to nie czyni go liderem. Mimo to różne pary można wielokrotnie usuwać, aby zobaczyć, jak wyglądałby ostatni zestaw. Pierwsze dwa elementy, 5 i 4 są różne. Jeśli zostaną usunięte, pozostały zestaw byłby, 7, 1, 7, 2, 3, 7, 8. W tym pozostałym zestawie 7 jest nadal dominującym elementem. Ale to wciąż nie jest lider pozostałego zestawu. Pamiętaj, że lider musi wystąpić ponad połowa liczby razy. Następne dwa elementy, 7 i 1 są różne. Jeśli zostaną usunięte, pozostały zestaw wynosiłby 7, 2, 3, 7, 8. 7 jest nadal dominującym elementem, ale wciąż nie jest liderem. Następne dwa elementy, 7 i 2 są różne. Są usunięte, aby mieć zestaw, 3, 7, 8. Tym razem nie ma głównego elementu i nie ma lidera. Następne dwa elementy, 3 i 7 są różne. Po ich usunięciu pozostały zestaw wynosiłby 8.

W przypadku poprzednich trzech wektorów końcowy pozostały element lub końcowe pozostałe same elementy są elementem większościowym. Wiadomo już, że w ostatnim wektorze nie ma elementu większości (lidera). Tak więc fakt, że element ostatecznie pozostaje, niekoniecznie oznacza, że ​​jest to element większości.

Teraz rozważ przypadek, w którym N jest liczbą parzystą, a każdy element w wektorze występuje raz. W takim przypadku wszystkie pary elementów zostaną usunięte i w końcowym zestawie nie pozostaną żadne elementy. Oczywiście w tym przypadku funkcja musi zwrócić -1, ponieważ nie ma elementu większościowego.

Dla końcowego pozostałego jednego elementu lub końcowego pozostałych samych elementów ma/trzeba sprawdzić, czy element występuje więcej niż połowa liczby razy w wektorze. Ten pozostały element nazywa się kandydatem.

O (n) Algorytm złożoności czasu dla elementu większościowego

Strategia polega na usuwaniu par elementów, które są wielokrotne, wielokrotnie: od lewej w danym wektorze. Jeśli żaden element nie pozostanie, nie ma elementu większości, a funkcja powinna zwrócić -1. Jeśli pozostało jeden lub więcej tych samych elementów, należy to sprawdzić, czy element występuje więcej niż połowa razy w wektorze. Ten element nazywa się kandydatem. Staje się elementem większości, jeśli występuje więcej niż połowa liczby razy.

To sprawdzenie można wykonać w czasie liniowym, skanując wektor z lewej i zatrzymać się, gdy tylko liczba występowania jest po prostu większa niż połowa długości wektora. Jeśli cały wektor jest skanowany, a liczba wystąpienia kandydata nie jest więcej niż połowa razy, to nie ma elementu większości (zgodnie z definicją).

Strategia z c++

Z C ++ elementy nie muszą być usuwane z danego wektora. Zamiast tego używany jest stos. Pierwszy element wektora jest wypychany na górę stosu. Jeśli następny element różni się od górnego elementu w stosie, wówczas górny element w stosie jest usuwany (wyskakuje); W przeciwnym razie ten następny element jest zepchnięty na górę stosu (jeśli górny element stosu i następny element są taki sam). Ten program trwa przez resztę elementów.

Na końcu skanowania (jeden przejście wektora), jeśli żaden element nie ma w stosie, nie ma elementu większościowego. Jeden lub więcej elementów może pozostać w stosie. Jeśli w stosie pozostaje więcej niż jeden element, te pozostałe elementy muszą być takie same. Ten element nazywa się kandydatem.

Niezależnie od tego, czy jeden lub więcej tego samego elementu pozostaje w stosie, ten element lub ten sam element występujący więcej niż raz jest możliwym elementem większości. Wektor musi zostać ponownie wycofany, aby sprawdzić, czy ten element występuje więcej niż połowa liczby razy dla całkowitej liczby elementów w wektorze. Jeśli wystąpi ponad połowa razy, to element ten jest elementem większości (lidera); W przeciwnym razie wektor (lub tablica) nie ma elementu większościowego (funkcja powinna zwrócić -1).

Kodowanie C ++

Ilekroć wektor jest używany w programie C ++, nagłówek programu musi być coś takiego:

#włączać
#włączać
#włączać
za pomocą przestrzeni nazw Std;

Biblioteka stosu musi być uwzględniona. Standardowa przestrzeń nazw jest używana. Wektor jest główną listą, więc jego biblioteka jest uwzględniona. Biblioteka iostream powinna być zawsze uwzględniona; Jest odpowiedzialny za wejście/wyjście. Nazwa funkcji algorytmu O (N) jest większością. Pierwsza połowa kodu funkcji to:

Większość (wektor &A)
int n = a.rozmiar();
int size = 0;
stos st;
St.push ([0]);
dla (int i = 1; iif (st.size ()> 0) // Aby uniknąć, błąd segmentacji (zrzucony rdzeń)
if ([i] == st.szczyt())
St.push ([i]);

w przeciwnym razie
St.Muzyka pop(); // Jeśli inny


w przeciwnym razie
St.push ([i]); // pchnij na górę stosu, jeśli jest pusty

Ma to pierwszy na pętlę, który jest głównym na pętlę. Przed pętlą, pierwszy element wektora jest wysyłany do stosu (góra). To narzędzia do pęknięcia na implementacja strategii C ++ jest wspomniana powyżej. Druga i ostatnia część funkcji większościowego () to:

int kandydat = -1;
if (st.size ()> 0)
kandydat = st.szczyt();
int lider = -1;
int count = 0;
dla (int i = 0; iif ([i] == kandydat)
Count += 1;


if (Count> n/2)
lider = kandydat;
przywódca powrotu;

To sprawdza, czy kandydat jest w rzeczywistości elementem większości. Zmienny lider jest synonimem elementu większości. Zmienny kandydat jest możliwym elementem większości. Gdy tylko wartość liczby przekracza N/2, wówczas kandydat jest elementem większościowym. Ta część ma pętlę, która sprawdza, czy wektor ma element większości. Powyższe dwie części należy połączyć, aby utworzyć jedną funkcję. Funkcja zwraca -1, jeśli nie ma elementu większości.

Odpowiednia główna funkcja C ++ dla powyższego kodu to:

wektor v1 = 6, 8, 4, 6, 8, 6, 6;
int ret1 = większość (v1);
Cout << ret1 << endl;
wektor v2 = 3, 4, 3, 2, 3, -1, 3, 3;
int ret2 = większość (v2);
Cout << ret2 << endl;
wektor v3 = 4, 3, 4, 4, 4, 2;
int ret3 = większość (v3);
Cout << ret3 << endl;
wektor v4 = 5, 4, 7, 1, 7, 2, 3, 7, 8;
int ret4 = większość (v4);
Cout << ret4 << endl;
powrót 0;

Złożoność czasu

Ponieważ istnieją dwa pętle, a wektor jest dwukrotnie skanowany, czytelnik może kusić, aby powiedzieć, że złożoność czasu jest, O (N+N). Teraz ciało pierwszej za pętla jest znacznie dłuższe niż ciało dla drugiego za pętla. Tak więc czas na wykonanie drugiego ciała na pętlę jest znacznie mniejszy niż czas na wykonanie pierwszego ciała na pętlę. Innymi słowy, ten czas dla drugiego ciała jest stosunkowo nieistotny. Tak więc złożoność czasu dla powyższego algorytmu jest cytowana jako:

NA)

Złożoność czasu to przybliżona liczba głównych operacji dla danej funkcji.

Wniosek

Ogólna strategia znalezienia elementu większości w O (n) czasu jest usuwanie par elementów, które są wielokrotnie, zaczynając od lewej na danej liście. Jeśli żaden element nie pozostał, wreszcie na liście, nie ma elementu większości, a funkcja powinna zwrócić -1. Jeśli pozostało jeden lub więcej tego samego elementu, należy go sprawdzić, czy element występuje więcej niż połowa razy na liście. Ten element nazywa się kandydatem. Jeśli kandydat wystąpi ponad połowa razy, na danej liście, kandydat jest elementem większościowym.

Chrys