Домінуючий елемент (Розбір)

Аналіз алгоритму

Нехай $x$ – мажоритарний елемент. Почнемо обробляти вхідні числа. Кожне число, рівне $x$, будемо класти в стек. При надходженні числа, не рівного $x$, будемо вилучати одне число зі стеку. Тоді в кінці обробки даних вершина стеку буде містити мажоритарний елемент.

Спочатку очистимо стек. При обробці чергового елемента $a$:

• якщо стек порожній, то push(a);

• якщо на вершині стеку знаходиться число $a$, то push(a);

• якщо на вершині стеку знаходиться число, не рівне $a$, то pop().

Якщо по закінченню обробки всіх чисел на вершині стеку є число $x$ (якщо стек порожній, то мажоранта немає), то слід перевірити, чи є воно мажоритарним елементом. Для цього слід порахувати, скільки разів число $x$ зустрічається в початковому наборі чисел. Якщо $x$ зустрічається більше \frac{n}{2} разів, то відповідь стверджувальна.

Оскільки в стеку в будь-який момент часу знаходиться одне число (можливо кілька разів), то змоделюємо стек двома змінними:

• $maj$ – число в стеку;

• $cnt$ – кількість разів, яке число $maj$ знаходиться в стеку;

Приклад

Розглянемо перший приклад. По закінченню алгоритму в стеці знаходиться 3. Перевіримо, чи є вона мажоритарним елементом. Для цього слід порахувати, скільки разів число 3 зустрічається в початковому масиві. Число 3 в масиві довжиною n = 7 зустрічається 4 рази. Оскільки 4 > \frac{n}{2}, то число 3 є мажоритарним елементом.

Реалізація алгоритму

Вхідну послідовність чисел збережемо в масиві m.

int m[110];

Оголосимо змінні maj і cnt для моделювання стеку:

• maj – число в стеку;

• cnt – кількість разів, яке число maj знаходиться в стеку;

int maj, cnt;

Читаємо вхідні дані.

scanf("%d",&n);
for(int i = 0; i < n; i++)
    scanf("%d",&m[i]);

Спочатку встановлюємо стек порожнім.

maj = 0; cnt = 0;

Обробляємо вхідні числа, моделюємо роботу стеку.

for(int i = 0; i < n; i++) {
    if (cnt == 0) {maj = m[i]; cnt++;}
    else if (m[i] == maj) cnt++;
    else cnt--;
}

У змінній cnt підрахуємо, скільки разів число maj зустрічається в масиві m.

cnt = 0;
for(int i = 0; i < n; i++)
    if (m[i] == maj) cnt++;

Якщо 2 * cnt > n, то мажорант існує. Інакше ні (res присвоїмо -1).

if(2 * cnt > n) res = maj; else res = -1;

Виводимо відповідь.

printf("%d\n",res);

Java реалізація

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m[] = new int[n];
        for(int i = 0; i < n; i++)
            m[i] = sc.nextInt();
        int maj = 0, cnt = 0;
        for(int i = 0; i < n; i++) {
            if (cnt == 0) {maj = m[i]; cnt++;}
            else if (m[i] == maj) cnt++;
            else cnt--;
        }
        cnt = 0;
        int res;
        for(int i = 0; i < n; i++)
            if (m[i] == maj) cnt++;
        if(2 * cnt > n) res = maj; else res = -1;
        System.out.println(res);
    }
}

Python реалізація

n = int(input())
m = list(map(int, input().split()))

maj = 0
cnt = 0

for num in m:
    if cnt == 0:
        maj = num
        cnt += 1
    elif num == maj:
        cnt += 1
    else:
        cnt -= 1

cnt = 0
for num in m:
    if num == maj: cnt += 1

if 2 * cnt > n: res = maj
else: res = -1

print(res)