}
==
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) |

== code(cpp) |

int countMajority(int n, int[] a, int k) {
     int[] b = new int[k];
    for (int i = 0; i < n; i++) {

}
==
Soluţia această este destul de eficientă în cazul menţionat anterior, dar când k este mult mai mare decât n, atunci această rezolvare ajunge să fie foarte lentă. Însă folosind o structură avansată de date putem să facem soluţia din nou eficientă. Această structură are la bază o tabelă de dispersie, ea mapează perechi de numere <cheie, valoare>, cheile vor fi numerele din şir, iar valorile vor fi numărul de apariţii al cheilor în şirul nostru.

== code(java) |

== code(cpp) |

int hashMajority(int n, int[] a) {
    HashMap<Integer, Integer> b = new HashMap<Integer, Integer>();
    for (int i = 0; i < n; i++) {

Această soluţie are complexitate O(n) ca timp, şi O(n) memorie suplimentară. Menţionăm că un dezavantaj al acestei soluţii ar fi că este una randomizată.
O altă soluţie care ar permite numărarea eficientă a numărului de apariţii a unui element în acest şir ar fi să sortăm şirul pentru că apoi elementele egale vor fi în poziţii consecutive.

== code(java) |

== code(cpp) |

int sortMajority(int n, int[] a) {
    Arrays.sort(a);
    int i = 0;

O idee ce ne vine pe urma acestei rezolvări este aceea că în şirul sortat, un element majoritar se va afla în şirul sortat şi pe poziţia n/2.Ştim că există algoritmi de selecţie care ne găsesc elemente de poziţie o fixată k din şirul sortat în complexitate O(n). Astfel vom găsi mai întâi elementul de pe poziţia n/2 iar apoi vom verifica dacă acesta este elementul majoritar al şirului. Astfel avem o soluţie de complexitate O(n) iar şirul iniţial va fi modificat. Există metode de selecţie nerandomizate, dar pentru uşurinţa implementării vom folosi una randomizată.

== code(java) |

== code(cpp) |

int  select(int n, int[] a, int left, int right, int k) {
    Random ran = new Random(System.currentTimeMilis());
    int i, j, aux, q;

O altă idee de rezolvare porneşte de la observaţia următoare: Dacă există un element majoritar în şir, atunci ultima lui cifră va fi elementul majoritar în şirul format din ultimele cifre a numerelor din şirul iniţial. Această observaţie este valabilă pentru orice cifră a numerelor nu doar ultima. Astfel putem determina pentru fiecare a x-a cifră a numemerelor care este cifra majoritară şi apoi să punem cap la cap cifrele majoritare pentru a forma numărul majoritar. Evident putem să folosim orice bază, dacă folosim baza b şi valoarea maximă a unui număr ar fi k atunci algoritmul va avea complexitatea O(n log in baza b din k) şi foloseşte memorie suplimentară O(b * log in baza b din k).  În practică putem considera acest algoritm ca fiind liniar. Să vedem o implementare a algoritmului pentru b = 1000 şi k = 999.999.999.

== code(java) |

== code(cpp) |

int digitMajority(int n, int[] a) {
     int[][] dig = new int[3][1000];
     for (int i = 0; i < n; i++) {

Realizăm acest algoritm parcurgând lista votanţilor şi ţinând un contor cu numărul de candidaţi k neîmperecheaţi până la pasul curent, evident dacă ei sunt neîmperecheaţi trebuie să susţină acelaşi candidat cand pentru că altfel am fi putut să cuplăm câţiva dintre ei.
Menţionăm că această rezolvare doar operaţii în care se verifică dacă două valori sunt identice, fapt ce se poate dovedi util pentru obiecte complexe care ar substitui candidaţii din problemă. Rezolvările anterioare s-au folosit de faptul că între elementele şirului ar exista o relaţie de ordine sau că am putea efectua asupra lor operaţii aritmetice.

== code(java) |

== code(cpp) |

int mooreMajority(int n, int[]  a) {
    int cand = -1, k = 0;
    for (int i = 0; i < n; i++) {

A doua soluţie este similară cu cea mai bună soluţie pentru prima problemă, numai că în loc să grupăm câte doi votanţi diferiţi vom grupa câte k votanţi cu păreri diferite.

== code(java) |

== code(cpp) |

int[] mooreKMajority(int n, int[]  a, int k) {
    int[] cand = new int[k - 1], notMatched = new int[k - 1],  num = new int[k-1];
    Arrays.fill(cand, -1);