Bojer-Murov algoritam preovlađujućeg elementa u linearnom vremenu[O(n)] i konstantnoj prostornoj složenosti [O(1)]. Problem preovlađujućeg elementa služi da se utvrdi da li u nekoj unapred zadatoj nisci postoji neki element koji je većinski, i ako postoji algoritam nam daje konkretan element. Matematički, za zadatu konačnu nisku (dužine n), cilj je pronaći element koji se pojavljuje više od [ n/2 ] puta.
Opis Algoritam se izvršava u dva koraka:
1. Eleminisati sve elemente osim jednog.
Iterirajući kroz nisku, održavamo trenutnog kandidata i brojač (brojač je inicijalno 0). Prolaskom kroz niz u svakom koraku uvećavamo vrednost brojača (Ukoliko naiđemo na element koga smo proglasili za kandaidata) inače smanjujemo brojač. U slučaju da je brojač 0, naredni element proglašavamo za kandidata i nastavljamo pretragu.
2. Provera da li je preostali kandidat zaista većinski.
Nakon što smo izdvojili potencijalnog kandidata u koraku 1, prolazimo kroz nisku i prebrojavamo broj pojavljivanja našeg kandidata. Ukoliko je broj pojavljivanja našeg kandidata veći od polovine dužine niske, tada je naš kandidat zaista većinski element. Inače naša niska nema većinski element.
Implementacije u C-u Algoritam Preovladjuje (x,n): ulaz: x, n /* niz pozitivnih brojeva x, dimenzije n*/ izlaz: preovlada /* preovladjujuci alaement (ako postoji) ili -1 */ C=x; M=1; for(i=1; i < n; i++) if (M==0) {C=x[i]; M=1;} else if (x[i]==C) M++; else M--; if (M==0) preovlada=-1; /*nema preovladjujuceg elementa*/ else brojac=0; for (i=0; i < n; i++) if (x[i]==C) brojac++; if (brojac > n/2) preovlada=C; else preovlada=-1;
Algoritam Preovladjuje (x,n): Ulaz x, n /* niz brojeva x, dimenzije n*/ Izlaz /* preovladjujuci element (ako postoji) ili -1 */ { C=x; M=1; for(i=1; i<n; i++){ if (M==0) { C=x[i]; M=1;
else { if (x[i]==C) M++; else M--;
if (M==0) return -1; /*nema preovladjujuceg elementa*/ else brojac=0; for (i=0; i < n; i++) if (x[i]==C) brojac++; if (brojac > n/2) return C; else return -1; }
Implementacija u Javi import java.util.*; public class MajorityVote { public int majorityElement(int[] num) { int n = num.length; int candidate = num, counter = 0; for (int i : num) { if (counter == 0) { candidate = i; counter = 1; } else { if (i == candidate) { counter++; } else { counter--;
counter = 0; for (int i : num) { if (i == candidate) counter++;
if (counter < (n + 1) / 2) return -1; return candidate;
public static void main(String[] args) { MajorityVote s = new MajorityVote(); System.out.format("%d\n", s.majorityElement(new int[] {1, 2, 3})); System.out.format("%d\n", s.majorityElement(new int[] {2, 2, 3}));
Spoljašnje veze
Primer izvršavanja programa
Категорија:Algoritmi