Majoritetselement med C ++

La n være antall elementer i en vektor eller matrise. Flertallet eller lederen er elementet som oppstår mer enn halvparten av tidene for alle elementene i vektoren. Halvparten av N betyr: Hvis n er 10, er halvparten av tiden 5. Elementet ved halve stillingen er ved indeks 4, for nullbasert indekstelling. Det minst heltallet som er mer enn halvparten av 10 er helt klart 6 (tilsvarende indeks 5). Hvis n er 11, regnes halvparten av n som fortsatt som 5. Dette er hele tallet tatt når 11 er delt av 2. Indeksen for halvparten er fremdeles 4 for nullbasert indeksering. Når N er 11, er det minst heltallet som er tydelig mer enn den bokstavelige halvdelen av 11 fremdeles 6 (tilsvarende indeks 5).

Så halvparten av lengden (størrelsen) på en vektor er resultatet av heltallsavdeling på N med 2. Det vil si at hele antallet av kvotienten, etter å ha delt seg med 2, blir tatt om det er en resten eller ikke.

Flertallet eller lederen er elementet som oppstår mer enn halvparten av tidene for alle elementene i vektoren eller matrisen. Det må være mer enn halvparten av tidene og ikke bare halvparten av tidene. Det vil si at det må være mer enn n/2 ganger (tar det resulterende hele nummeret). Funksjonen skal returnere -1, hvis det ikke eksisterer flertallselement.

Denne artikkelen forklarer hvordan du bestemmer flertallet for en tidskompleksitet av O (n). Det vil si at maksimalt N -hovedoperasjoner er nødvendig for å oppnå flertallets element.

Vektoreksempler

Tenk på følgende vektor:

vektor A = 6, 8, 4, 6, 8, 6, 6

Flertallet (lederen) er 6. Det forekommer 4 ganger av 7 ganger (elementer).

Tenk på følgende vektor:

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

Flertallet er 3. Det forekommer 5 ganger av 8 elementer.

Tenk på følgende vektor:

vektor C = 4, 3, 4, 4, 4, 2

Flertallet er 4. Det forekommer 4 ganger av 6 elementer.

Tenk på følgende vektor:

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

Det er ikke noe flertall element her. Så funksjonen må returnere -1. Det er ni elementer her. Antallet, 7, forekommer tre ganger, og hvert av de andre elementene oppstår en gang. Tre er ikke mer enn halvparten av ni. Et akseptabelt majoritetselement burde ha skjedd, minst 5 ganger.

Illustrasjon for algoritme for O (n) tidskompleksitet

Fra følgende vektorer fjernes to forskjellige elementer samtidig.

Vurder igjen vektoren:

vektor A = 6, 8, 4, 6, 8, 6, 6

Lederens (flertall) element er 6. De to første elementene er forskjellige. Hvis begge er fjernet, vil det gjenværende settet være, 4, 6, 8, 6, 6. I dette gjenværende settet er 6 fortsatt leder: tre ganger av 5 ganger. De to neste elementene, 4 og 6 er forskjellige. Hvis de fjernes, vil det gjenværende settet være 8, 6, 6. I det gjenværende settet er 6 fremdeles lederen. De to neste elementene, 8 og 6 er forskjellige. Hvis de fjernes, vil det gjenværende settet være 6. I dette siste settet med bare ett element er 6 fremdeles lederen. Det ser derfor ut som om to forskjellige tall fjernes gjentatte ganger. Det endelige gjenværende elementet ville være majoritetselementet.

Tenk nå på vektoren:

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

Lederens (majoritet) element er 3. De to første elementene er forskjellige. Hvis begge blir fjernet, vil det gjenværende settet være, 3, 2, 3, -1, 3, 3. I dette gjenværende settet er 3 fortsatt leder: fire ganger av seks ganger. De neste to elementene, 3 og 2 er forskjellige. Hvis de fjernes, vil det gjenværende settet være 3, -1, 3, 3. I det gjenværende settet er 3 fremdeles lederen. De neste to elementene, 3 og -1 er forskjellige. Hvis de fjernes, vil det gjenværende settet være 3, 3. I dette siste settet med to elementer er 3 fremdeles lederen. Det ser derfor fremdeles ut som om to forskjellige tall fjernes gjentatte ganger. De siste de samme gjenværende elementene ville være flertallets element.

Vurder neste vektoren:

vektor C = 4, 3, 4, 4, 4, 2

Lederens (flertall) element er 4. De to første elementene er forskjellige. Hvis begge er fjernet, vil det gjenværende settet være, 4, 4, 4, 2. I dette gjenværende settet er 4 fortsatt leder: tre ganger av fire ganger. De neste to elementene, 4 og 4 er de samme, og de skal ikke fjernes. Imidlertid kan det første elementet her, og det tredje elementet her, vurderes for fjerning. Det hender at disse to også er de samme. Fortsatt kan det første elementet og det fjerde elementet vurderes for fjerning. De er forskjellige, så de blir fjernet. Det gjenværende siste settet er 4, 4. Det ser derfor fremdeles ut som om to forskjellige tall fjernes gjentatte ganger. Den siste gjenværende samme elementene ville være majoritetselementet.

Tenk da på vektoren:

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

Vi vet allerede at denne vektoren ikke har noen leder, selv om 7 forekommer tre ganger og hvert annet antall oppstår en gang. 7 forekommer tre av ni ganger, og det gjør det ikke til leder. Fortsatt kan forskjellige par fjernes gjentatte ganger for å se hvordan det endelige gjenværende settet vil se ut. De to første elementene, 5 og 4 er forskjellige. Hvis de fjernes, vil det gjenværende settet være, 7, 1, 7, 2, 3, 7, 8. I dette gjenværende settet er 7 fremdeles det dominerende elementet. Men det er ikke fremdeles lederen for det gjenværende settet. Husk at lederen må forekomme mer enn halvparten av antall ganger. De to neste elementene, 7 og 1 er forskjellige. Hvis de fjernes, vil det gjenværende settet være 7, 2, 3, 7, 8. 7 er fremdeles det dominerende elementet, men det er fremdeles ikke lederen. De to neste elementene, 7 og 2 er forskjellige. De fjernes for å ha settet, 3, 7, 8. Det er ikke noe dominerende element som er igjen denne gangen, og det er ingen leder. De neste to elementene, 3 og 7 er forskjellige. Når de fjernes, vil det gjenværende settet være 8.

For de tre foregående vektorene er det endelige gjenværende elementet eller den endelige gjenværende samme elementene majoritetselementet. Det er allerede kjent at det ikke er noe flertall (leder) element i denne siste vektoren. Så det faktum at et element endelig gjenstår, betyr ikke nødvendigvis at det er flertallets element.

Vurder nå saken der n er et jevnt tall og hvert element i vektoren oppstår en gang. I dette tilfellet vil alle par av elementer bli fjernet, og det vil ikke være noe element som gjenstår i det endelige settet. Det er klart, i dette tilfellet, må funksjonen returnere -1 da det ikke er noe flertallselement.

For den endelige gjenværende elementet eller den endelige gjenværende samme elementene må/må sjekkes hvis elementet oppstår mer enn halvparten av antall ganger i vektoren. Dette gjenværende elementet kalles kandidaten.

O (n) tidskompleksitetsalgoritme for majoritetselement

Strategien er å fjerne par elementer som er forskjellige, gjentatte ganger: å begynne fra venstre i den gitte vektoren. Hvis ikke noe element er igjen, er det ikke noe flertallselement og funksjonen skal returnere -1. Hvis ett eller flere av de samme elementene er igjen, må det sjekkes hvis elementet oppstår mer enn halvparten av tidene i vektoren. Dette elementet kalles kandidaten. Det blir flertallets element hvis det forekommer mer enn halvparten av antall ganger.

Denne kontrollen kan gjøres i lineær tid, ved å skanne vektoren fra venstre, og for å stoppe så snart antall forekomster er bare større enn halvparten av vektoren. Hvis hele vektoren blir skannet, og antall ganger kandidaten oppstår er ikke mer enn halvparten av tidene, er det ikke noe flertall element (i henhold til definisjonen).

Strategi med c++

Med C ++ trenger ikke elementene fjernes fra den gitte vektoren. I stedet brukes en stabel. Det første elementet i vektoren skyves inn i toppen av stabelen. Hvis det neste elementet er forskjellig fra toppelementet i stabelen, fjernes toppelementet i stabelen (spratt av); Ellers skyves dette neste elementet til toppen av stabelen (hvis stakkets toppelement og dette neste elementet, er det samme). Denne ordningen fortsetter for resten av elementene.

På slutten av skanning (en passering av vektoren), hvis ingen element er i stabelen, er det ikke noe flertallselement. Ett eller flere elementer kan forbli i stabelen. Hvis mer enn ett element forblir i stabelen, må disse gjenværende elementene være de samme. Dette elementet kalles kandidaten.

Enten ett eller flere av det samme elementet er igjen i stabelen, er det elementet eller det samme elementet som oppstår mer enn en gang et mulig flertall element. Vektoren må skannes på nytt for å se om dette elementet oppstår mer enn halvparten av antall ganger for det totale antall elementer i vektoren. Hvis det forekommer mer enn halvparten av tidene, er det elementet flertallet (leder) element; Ellers har vektoren (eller matrisen) ikke noe flertall element (funksjonen skal returnere -1).

C ++ koding

Hver gang en vektor brukes i et C ++ -program, må overskriften på programmet være noe sånt som:

#inkludere
#inkludere
#inkludere
ved hjelp av navneområdet STD;

Stabelbiblioteket må inkluderes. Standard navneområde brukes. Vektor er hovedlisten, så biblioteket er inkludert. IOSTREAM -biblioteket skal alltid inkluderes; Det er ansvarlig for inngang/utgang. Navnet på funksjonen for o (n) algoritmen er majoritetselement. Den første halvdelen av funksjonskoden er:

int majoritetselement (vektor & A)
int n = a.størrelse();
int størrelse = 0;
stable st;
st.push (a [0]);
for (int i = 1; iif (st.størrelse ()> 0) // for å unngå, segmenteringsfeil (kjernedumped) feil
if (a [i] == st.topp ())
st.push (a [i]);

annet
st.pop (); // hvis annerledes


annet
st.push (a [i]); // trykk til toppen av stabelen hvis det er tomt

Dette har den første for-loopen som er den viktigste for-loop. Før for-loopen blir det første elementet i vektoren sendt til stabelen (toppen). Denne for-loop implementerer C ++ -strategien er nevnt ovenfor. Den andre og siste delen av flertallet () -funksjonen er:

int -kandidat = -1;
if (st.størrelse ()> 0)
Kandidat = ST.topp();
int leder = -1;
int count = 0;
for (int i = 0; iif (a [i] == kandidat)
telle += 1;


if (count> n/2)
leder = kandidat;
returleder;

Dette sjekker om kandidaten faktisk er majoritetselementet. Den variable lederen er et synonym av flertallets element. Den variable kandidaten er det mulige majoritetselementet. Så snart verdien for tellingen overstiger N/2, er kandidaten flertallets element. Denne delen har for-loop som sjekker om vektoren har et flertall element. Ovennevnte to deler skal kobles sammen for å danne en funksjon. Funksjonen returnerer -1, hvis det ikke eksisterer flertallselement.

En passende C ++ hovedfunksjon, for ovennevnte kode er:

vektor v1 = 6, 8, 4, 6, 8, 6, 6;
int ret1 = flertall (v1);
cout << ret1 << endl;
vektor v2 = 3, 4, 3, 2, 3, -1, 3, 3;
int ret2 = flertall (v2);
cout << ret2 << endl;
vektor v3 = 4, 3, 4, 4, 4, 2;
int ret3 = flertall (v3);
cout << ret3 << endl;
vektor v4 = 5, 4, 7, 1, 7, 2, 3, 7, 8;
int ret4 = flertall (v4);
cout << ret4 << endl;
retur 0;

Tidskompleksitet

Siden det er to for-løkker med vektoren som skannes to ganger, kan leseren bli fristet til å si at tidskompleksiteten er, o (n+n). Nå er kroppen til den første for-loop mye lenger enn kroppen for den andre for-loop. Så tiden for den andre for-loop-kroppen å utføre er mye mindre enn tiden for den første for-loop-kroppen å utføre. Med andre ord, den gangen for den andre kroppen er relativt ubetydelig. Så tidskompleksiteten for ovennevnte algoritme er sitert som:

På)

Tidskompleksitet er det omtrentlige antallet hovedoperasjoner for den aktuelle funksjonen.

Konklusjon

Den generelle strategien for å finne majoritetselementet i O (n) tid er å fjerne par elementer som er forskjellige, gjentatte ganger, fra venstre i den gitte listen. Hvis ikke noe element er igjen, endelig på listen, er det ikke noe flertallselement og funksjonen skal returnere -1. Hvis ett eller flere av det samme elementet er igjen, må det sjekkes hvis elementet oppstår mer enn halvparten av tidene på listen. Dette elementet kalles kandidaten. Hvis kandidaten forekommer mer enn halvparten av tidene, i den gitte listen, er kandidaten flertallets element.

Chrys