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

Пусть $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)