(Categoria _Algoritmi_, Autor _Cosmin Negruşeri_)

În acest articol dezbatem problema dezvoltării de algoritmi eficienţi pentru determinarea candidatului care a întrunit un număr majoritar de voturi.
Problema enunţată formal este următoarea: Se dă un şir de n numere naturale, se cere determinarea unui element care apare de cel puţin [n/2]+1 ori în şir dacă există un astfel de element în şir.

== code(java) |
int bruteForceMajority(int n, int[] a)
    for (int i = 0; i < n; i++) {

          int nr = 0;
          for (int j = 0; j < n; j++) {
               if (a[j]==a[i]) nr++;

        int nr = 0;
        for (int j = 0; j < n; j++) {
            if (a[j]==a[i]) nr++;

          }

          if  (nr > n / 2) return a[i];

        if  (nr > n / 2) return a[i];

    }
    return -1;
}

Dacă numerele din şir aparţin unei mulţimi {1, 2, ... k} iar acest k este mic comparativ cu n, atunci putem să îmbunătăţinm ideea de mai devreme şi să folosim un şir auxiliar b, unde b[x] va număra de câte ori apare un număr x în şirul nostru. Această soluţie are complexitate O(n + k) ca timp şi O(n + k) ca spaţiu.
== code(java) |
int countMajority(int n, int[] a, int k) {

     int[] b = new int[k];

    int[] b = new int[k];

    for (int i = 0; i < n; i++) {

         b[a[i]]++;//incrementăm numărul de apariţii al elementului a[i]

        b[a[i]]++;//incrementăm numărul de apariţii al elementului a[i]

    }
    for (int i = 0; i < k; i++) {
         if (b[i] > n/2) return i;