940. Мажорирующий элемент

Задан массив длины n, найдите его мажорирующий элемент. Элемент называется мажорирующим, если он встречается в массиве более раз.

Вход. Первая строка содержит число n (1 ≤ n ≤ 100). Вторая строка содержит n натуральных чисел.

Выход. Если массив содержит мажорирующий элемент, то выведите его. Иначе выведите -1.

Пример входа 1	Пример выхода 1
7 3 3 5 4 2 3 3	3
Пример входа 2	Пример выхода 2
4 2 3 2 3	-1

РЕШЕНИЕ

стек

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

Пусть x – мажорирующий элемент. Начнем обрабатывать входные числа. Каждое число, равное x, будем класть в стек. При поступлении числа, не равного x, будем извлекать одно число из стека. Тогда в конце обработки данных вершина стека будет содержать мажорирующий элемент.

Изначально очистим стек. При обработке очередного элемента a:

· если стек пустой, то push(a);

· если на вершине стека находится число a, то push(a);

· если на вершине стека находится число, не равное a, то pop();

Если по окончанию обработки всех чисел на вершине стека имеется число x (если стек пустой, то мажоранты нет), то следует проверить, является ли оно мажорирующим элементом. Для этого следует посчитать, сколько раз число x встречается в исходном наборе чисел. Если x встречается более раз, то ответ утвердительный.

Поскольку в стеке в любой момент времени находится одно число (возможно несколько раз), то промоделируем стек двумя переменными:

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

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

Пример

Рассмотрим первый пример.

По окончанию алгоритм стеке находится 3. Проверим, является ли она мажорирующим элементом. Для этого следует посчитать, сколько раз число 3 встречается в исходном массиве. Число 3 в массиве длины n = 7 встречается 4 раза. Поскольку 4 > , что число 3 является мажорирующим элементом.

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

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

int m[110];

Объявим переменные maj и cnt для моделирования стека:

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

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

int maj, cnt;

Читаем входные данные.

scanf("%d",&n);

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

scanf("%d",&m[i]);

Изначально устанавливаем стек пустым.

maj = 0; cnt = 0;

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

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

{

Если стек пустой (cnt = 0), то кладем в него элемент m[i].

if (cnt == 0) {maj = m[i]; cnt++;}

Если текущий элемент m[i] совпадает с вершиной стека maj, то кладем m[i] в стек.

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++;

Если cnt > , то мажоранта существует. Иначе нет (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; // cnt > nums.size() / 2

System.out.println(res);

}

}

Python реализация

Читаем входные данные.

n = int(input())

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

Объявим переменные maj и cnt для моделирования стека:

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

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

Изначально устанавливаем стек пустым.

maj = 0

cnt = 0

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

for num in m:

Если стек пустой (cnt = 0), то кладем в него элемент num.

if cnt == 0:

maj = num

cnt += 1

Если текущий элемент num совпадает с вершиной стека maj, то кладем num в стек.

elif num == maj:

cnt += 1

Иначе извлекаем элемент из стека.

else:

cnt -= 1

В переменной cnt подсчитаем, сколько раз число maj встречается в списке m.

cnt = 0

for num in m:

if num == maj: cnt += 1

Если cnt > , то мажоранта существует. Иначе нет (res присвоим -1).

if 2 * cnt > n: res = maj

else: res = -1

Выводим ответ.

print(res)