169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊n/2⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

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

Задан массив длины n. Мажорирующим называется элемент, встречающийся в нем больше чем ⌊n/2⌋ раз.

Считайте, что массив не пустой, а мажорирующий элемент всегда существует.

// C++

class Solution {

public:

int majorityElement(vector<int>& nums) {

}

};

// Java

public class Solution {

public int majorityElement(int[] nums) {

}

}

SOLUTION

stack

Algorithm analysis

Let’s simulate the stack processing that can contain only one value multiple times. For this it is enough only two variables:

· maj – the element in the stack;

· cnt – number of times the value maj is pushed into the stack.

Initially the stack is empty (cnt = 0). Then process the elements of array nums:

· if stack is empty, push nums[i] into the stack.

· if nums[i] is on the top of the stack, push nums[i] into the stack (increase cnt by 1).

· Otherwise pop the top element from the stack (decrease cnt by 1).

The statement says that majority element always exists. After processing all elements of array the majority element will be on the top of the stack.

РЕШЕНИЕ

стек

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

Будем моделировать работу стека, способного содержать только одно значение произвольное количество раз. Для этого нам достаточно две переменные:

· maj – элемент, содержащийся в стеке;

· cnt – количество раз, которое элемент maj положили в стек.

Сначала стек пустой (cnt = 0). Далее обрабатываем элементы массива nums:

· если стек пустой, то заносим nums[i] в стек.

· если на вершине стека лежит значение nums[i], кладем nums[i] в стек (увеличиваем cnt на 1).

· иначе удаляем верхний элемент со стека (уменьшаем cnt на 1).

В условии задачи сказано, что мажорирующий элемент обязательно существует. Тогда после обработки массива он обязательно останется на вершине стека.

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

class Solution

{

public:

int majorityElement(vector<int>& nums)

{

int maj = 0, cnt = 0;

for(int i = 0; i < nums.size(); i++)

{

Стек пуст, если cnt = 0. Приходит элемент nums[i]. Кладем его в стек, присваивая nums[i] переменной maj, и устанавливая cnt равным 1.

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

Стек не пустой. Если приходит такой же элемент, что и в стеке (nums[i] = maj), то заносим nums[i] в стек.

else if (nums[i] == maj) cnt++;

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

else cnt--;

}

Поскольку мажорирующий элемент в массиве существует, то в конце обработки массива он останется на вершине стека.

return maj;

}

};

Java реализация

public class Solution

{

public int majorityElement(int[] nums)

{

int maj = 0, cnt = 0;

for(int i = 0; i < nums.length; i++)

{

if (cnt == 0)

{

maj = nums[i];

cnt++;

}

else

if (nums[i] == maj)

cnt++;

else

cnt--;

}

return maj;

}

}