229. Majority Element II

Given an integer array of size n, find all elements that appear more than times. The algorithm should run in linear time and in O(1) space.

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

Задан массив длины n. Найдите в нем все элементы, которые встречаются более чем раз. Время алгоритма должно быть линейным, потребление памяти O(1) (константным).

// C++

class Solution {

public:

vector<int> majorityElement(vector<int>& nums) {

}

};

// Java

public class Solution {

public List<Integer> majorityElement(int[] nums) {

}

}

РЕШЕНИЕ

стек

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

Массив nums может содержать не более двух мажорирующих элементов. Заведем два стека, каждый из которых в процессе обработки будет содержать элемент, который может быть мажорирующим. Каждый стек будет содержать только одно значение произвольное количество раз, поэтому их работу моделируем двумя переменными: maj₁ и cnt₁ для первого стека, maj₂ и cnt₂ для второго.

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

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

· если один из стеков пуст, но при этом nums[i] не находится во втором стеке (или оба стека пусты), то заносим nums[i] в стек.

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

Теперь следует проверить, являются ли maj₁ и maj₂ мажорирующими. Подсчитаем, сколько раз они встречаются в массиве nums. Если их количество в массиве превышает , то заносим эти элементы в результирующий массив.

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

class Solution

{

public:

vector<int> majorityElement(vector<int>& nums)

{

if (nums.size() == 0) return nums;

int i, cnt1 = 0, cnt2 = 0, maj1 = 0, maj2 = 0;

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

if (maj1 == nums[i])

cnt1++;

else if (maj2 == nums[i])

cnt2++;

else if (cnt1 == 0)

{

maj1 = nums[i];

cnt1 = 1;

} else if (cnt2 == 0)

{

maj2 = nums[i];

cnt2 = 1;

} else

{

cnt1--;

cnt2--;

}

vector<int> res;

cnt1 = cnt2 = 0;

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

if (maj1 == nums[i])

cnt1++;

else if (maj2 == nums[i])

cnt2++;

if (cnt1 > nums.size() / 3)

res.push_back(maj1);

if (cnt2 > nums.size() / 3)

res.push_back(maj2);

return res;

}

};

Java реализация

public class Solution

{

public List<Integer> majorityElement(int[] nums)

{

List<Integer> res = new ArrayList<Integer>();

if (nums.length == 0) return res;

int cnt1 = 0, cnt2 = 0, maj1 = 0, maj2 = 0;

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

if (maj1 == nums[i])

cnt1++;

else if (maj2 == nums[i])

cnt2++;

else if (cnt1 == 0)

{

maj1 = nums[i];

cnt1 = 1;

} else if (cnt2 == 0)

{

maj2 = nums[i];

cnt2 = 1;

} else

{

cnt1--;

cnt2--;

}

cnt1 = cnt2 = 0;

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

if (maj1 == nums[i])

cnt1++;

else if (maj2 == nums[i])

cnt2++;

if (cnt1 > nums.length / 3)

res.add(maj1);

if (cnt2 > nums.length / 3)

res.add(maj2);

return res;

}

}