Бојер-Муров алгоритам већинског гласа
Бојер-Муров алгоритам преовлађујућег елемента у линеарном времену[О(н)] и константној просторној сложености [О(1)]. Проблем преовлађујућег елемента служи да се утврди да ли у некој унапред задатој нисци постоји неки елемент који је већински, и ако постоји алгоритам нам даје конкретан елемент. Математички, за задату коначну ниску (дужине н), циљ је пронаћи елемент који се појављује више од [ н/2 ] пута.
Опис[уреди | уреди извор]
Алгоритам се извршава у два корака:
1. Елеминисати све елементе осим једног.
Итерирајући кроз ниску, одржавамо тренутног кандидата и бројач (бројач је иницијално 0). Проласком кроз низ у сваком кораку увећавамо вредност бројача (Уколико наиђемо на елемент кога смо прогласили за кандаидата) иначе смањујемо бројач. У случају да је бројач 0, наредни елемент проглашавамо за кандидата и настављамо претрагу.
2. Провера да ли је преостали кандидат заиста већински.
Након што смо издвојили потенцијалног кандидата у кораку 1, пролазимо кроз ниску и пребројавамо број појављивања нашег кандидата. Уколико је број појављивања нашег кандидата већи од половине дужине ниске, тада је наш кандидат заиста већински елемент. Иначе наша ниска нема већински елемент.
Имплементације у C-у[уреди | уреди извор]
Algoritam Preovladjuje (x,n):
ulaz: x, n /* niz pozitivnih brojeva x, dimenzije n*/
izlaz: preovlada /* preovladjujuci alaement (ako postoji) ili -1 */
C=x[0];
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[0];
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;
}
Имплементација у Јави[уреди | уреди извор]
import java.util.*;
public class MajorityVote {
public int majorityElement(int[] num) {
int n = num.length;
int candidate = num[0], 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}));
}
}
Спољашње везе[уреди | уреди извор]
- [1]
- Пример извршавања програма
- [2] Архивирано на сајту Wayback Machine (31. децембар 2016)