Матч 41, Мажорующий элемент (MajorityElement)

Массив содержит мажорующий элемент x если он встречается в массиве строго больше половины раз. По заданному массиву вернуть мажорующий элемент или -1, если такого не существует.

Класс: MajorityElement

Метод: int findMajorityElement(vector<int> a)

Ограничения: a содержит от 1 до 50 элементов, 0 £ a[i] £ 1000.

Вход. Массив чисел а.

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

Пример входа

a

{3, 9, 3, 3, 7}

{0, 1000, 984, 0}

{5}

Пример выхода

3

-1

5

РЕШЕНИЕ

обработка последовательностей

Для решения задачи будем использовать стек, который изначально пуст. Будем последовательно просматривать числа массива и совершать следующие операции:

1. Если стек пуст или вершина стека содержит текущий просматриваемый элемент массива, то заносим текущий элемент в стек.

2. Иначе удаляем элемент из вершины стека.

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

Можно заметить, что в стеке может находиться только одно число. Поэтому работу стека можно промоделировать при помощи двух переменных:

num – число находящееся в стеке;

cnt – количество чисел num, находящихся в стеке.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <stack>

using namespace std;

stack<int> s;

class MajorityElement

{

public:

int findMajorityElement(vector<int> a)

{

int i,c;

for(i=0;i<a.size();i++)

if (s.empty() || s.top() == a[i]) s.push(a[i]);

else s.pop();

if (s.empty()) return -1;

for(c=i=0;i<a.size();i++)

if (a[i] == s.top()) c++;

if (2*c > a.size()) return s.top();

return -1;

}

};

Промоделируем работу стека двумя переменными.

#include <cstdio>

#include <vector>

using namespace std;

class MajorityElement

{

public:

int findMajorityElement(vector<int> a)

{

int num, cnt, i, c;

// num = number in stack

// cnt = how many num's are in stack

for(num = cnt = i = 0; i < a.size(); i++)

if ((!cnt) || (num == a[i])) cnt++, num = a[i];

else cnt--;

if (!cnt) return -1;

for(c=i=0;i<a.size();i++)

if (a[i] == num) c++;

if (2*c > a.size()) return num;

return -1;

}

};