Бојер-Муров алгоритам већинског гласа

Бојер-Муров алгоритам преовлађујућег елемента у линеарном времену[О(н)] и константној просторној сложености [О(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)