Пусть n будет количеством элементов в векторе или массиве. Элемент большинства или лидер — это элемент, который встречается более чем в половине раз среди всех элементов вектора. Половина n означает: если n равно 10, то половина времени равна 5. Элемент в половине позиции находится в индексе 4 для подсчета индексов с нуля. Наименьшее целое число, которое больше половины от 10, очевидно, равно 6 (соответствует индексу 5). Если n равно 11, то половина n по-прежнему считается равной 5. Это целое число, полученное при делении 11 на 2. Индекс половины по-прежнему равен 4 для индексации с отсчетом от нуля. Когда n равно 11, наименьшее целое число, явно превышающее буквальную половину 11, по-прежнему равно 6 (соответствует индексу 5).
Итак, половина длины (размера) вектора является результатом целочисленного деления n на 2. То есть берется целое число частного после деления на 2 независимо от того, есть ли остаток.
Элемент большинства или лидер — это элемент, который встречается более чем в половине раз среди всех элементов вектора или массива. Это должно быть больше, чем в половине случаев, а не только в половине случаев. То есть оно должно быть больше n/2 раз (принимая полученное целое число). Функция должна возвращать −1, если не существует мажоритарного элемента.
В этой статье объясняется, как определить мажоритарный элемент для временной сложности O(n). То есть для получения мажоритарного элемента требуется максимум n основных операций.
Векторные примеры
Рассмотрим следующий вектор:
vector<int> A = {6, 8, 4, 6, 8, 6, 6}
Мажоритарный элемент (лидер) равен 6. Встречается 4 раза из 7 (элементов).
Рассмотрим следующий вектор:
vector<int> B = {3, 4, 3, 2, 3, —1, 3, 3}
Мажоритарный элемент равен 3. Он встречается 5 раз из 8 элементов.
Рассмотрим следующий вектор:
vector<int> C = {4, 3, 4, 4, 4, 2}
Мажоритарный элемент равен 4. Он встречается 4 раза из 6 элементов.
Рассмотрим следующий вектор:
vector<int> D = {5, 4, 7, 1, 7, 2, 3, 7, 8}
Здесь нет элемента большинства. Итак, функция должна вернуть −1. Здесь девять элементов. Число 7 встречается три раза, а каждый из остальных элементов встречается один раз. Три не больше половины девяти. Приемлемый элемент большинства должен был произойти, по крайней мере, 5 раз.
Иллюстрация алгоритма для временной сложности O(n)
Из следующих векторов одновременно удаляются два разных элемента.
Рассмотрим снова вектор:
vector<int> A = {6, 8, 4, 6, 8, 6, 6}
Лидер (большинство) элемент равен 6. Первые два элемента различны. Если удалить их оба, оставшийся набор будет {4, 6, 8, 6, 6}. В этом оставшемся наборе 6 по-прежнему лидирует: три раза из 5 раз. Следующие два элемента, 4 и 6, различны. Если их удалить, оставшийся набор будет {8, 6, 6}. В оставшемся наборе 6 по-прежнему лидирует. Следующие два элемента, 8 и 6, различны. Если их удалить, оставшийся набор будет {6}. В этом последнем наборе, состоящем только из одного элемента, 6 по-прежнему лидирует. Таким образом, создается впечатление, что два разных числа удаляются повторно. Последний оставшийся элемент будет элементом большинства.
Рассмотрим теперь вектор:
vector<int> B = {3, 4, 3, 2, 3, —1, 3, 3}
Элемент лидера (большинства) равен 3. Первые два элемента различны. Если оба они удалены, оставшийся набор будет {3, 2, 3, −1, 3, 3}. В этом оставшемся наборе 3 по-прежнему лидирует: четыре раза из шести. Следующие два элемента, 3 и 2, различны. Если их удалить, оставшийся набор будет {3, −1, 3, 3}. В оставшемся наборе 3 по-прежнему лидирует. Следующие два элемента, 3 и −1, различны. Если их удалить, оставшийся набор будет {3, 3}. В этом последнем наборе из двух элементов 3 по-прежнему лидирует. Поэтому все еще выглядит так, как будто два разных числа удаляются повторно. Последние же оставшиеся элементы будут элементом большинства.
Рассмотрим следующий вектор:
vector<int> C = {4, 3, 4, 4, 4, 2}
Элемент лидера (большинства) равен 4. Первые два элемента различны. Если оба они удалены, оставшийся набор будет {4, 4, 4, 2}. В этом оставшемся наборе 4 по-прежнему лидирует: три раза из четырех. Следующие два элемента, 4 и 4 одинаковые и их не надо удалять. Однако первый элемент здесь и третий элемент здесь можно считать подлежащими удалению. Бывает, что эти два тоже одинаковые. Тем не менее, первый элемент и четвертый элемент могут быть рассмотрены для удаления. Они разные, поэтому их удаляют. Оставшийся последний набор {4, 4}. Поэтому все еще выглядит так, как будто два разных числа удаляются повторно. Последние оставшиеся одинаковые элементы будут элементом большинства.
Рассмотрим вектор:
vector<int> D = {5, 4, 7, 1, 7, 2, 3, 7, 8}
Мы уже знаем, что у этого вектора нет лидера, хотя 7 встречается три раза, а каждое другое число встречается один раз. Число 7 встречается три раза из девяти, и это не делает его лидером. Тем не менее, разные пары можно удалять несколько раз, чтобы увидеть, как будет выглядеть окончательный оставшийся набор. Первые два элемента, 5 и 4, разные. Если их удалить, оставшийся набор будет {7, 1, 7, 2, 3, 7, 8}. В этом оставшемся наборе 7 по-прежнему является преобладающим элементом. Но это еще не лидер оставшегося набора. Помните, что лидер должен встречаться более половины числа раз. Следующие два элемента, 7 и 1, различны. Если их удалить, оставшийся набор будет {7, 2, 3, 7, 8}. 7 по-прежнему является преобладающим элементом, но все же не лидером. Следующие два элемента, 7 и 2, различны. Они удаляются, чтобы получить набор {3, 7, 8}. На этот раз не осталось преобладающего элемента и нет лидера. Следующие два элемента, 3 и 7, различны. Когда они будут удалены, оставшийся набор будет {8}.
Для трех предыдущих векторов последний оставшийся элемент или последние оставшиеся одинаковые элементы являются мажоритарным элементом. Уже известно, что в этом последнем векторе нет мажоритарного (лидерского) элемента. Таким образом, тот факт, что элемент, наконец, остался, не обязательно означает, что он является элементом большинства.
Теперь рассмотрим случай, когда n — четное число и каждый элемент вектора встречается один раз. В этом случае все пары элементов будут удалены, и в конечном наборе не останется ни одного элемента. Ясно, что в этом случае функция должна вернуть −1, так как нет мажоритарного элемента.
Для последнего оставшегося одного элемента или последних оставшихся одинаковых элементов необходимо/должны быть проверены, если элемент встречается более половины количества раз в векторе. Этот оставшийся элемент называется кандидатом.
O(n) Алгоритм временной сложности для мажоритарного элемента
Стратегия состоит в многократном удалении пар различных элементов: начиная слева в заданном векторе. Если элементов не осталось, значит, мажоритарного элемента нет, и функция должна вернуть −1. Если остался один или несколько одинаковых элементов, необходимо проверить, встречается ли этот элемент в векторе более половины раз. Этот элемент называется кандидатом. Он становится мажоритарным элементом, если встречается более половины числа раз.
Эту проверку можно выполнить за линейное время, сканируя вектор слева, и остановить, как только количество вхождений станет чуть больше половины длины вектора. Если сканируется весь вектор, а количество раз, когда кандидат встречается не более половины раз, то мажоритарного элемента нет (согласно определению).
Стратегия с C++
В C++ элементы не нужно удалять из заданного вектора. Вместо этого используется стек. Первый элемент вектора помещается на вершину стека. Если следующий элемент отличается от верхнего элемента в стеке, то верхний элемент в стеке удаляется (выскакивает); в противном случае этот следующий элемент помещается на вершину стека (если верхний элемент стека и этот следующий элемент совпадают). Эта схема продолжается для остальных элементов.
В конце сканирования (один проход вектора), если в стеке нет ни одного элемента, мажоритарного элемента нет. Один или несколько элементов могут остаться в стеке. Если в стеке остается более одного элемента, то эти оставшиеся элементы должны быть одинаковыми. Этот элемент называется кандидатом.
Независимо от того, остались ли в стеке один или несколько одинаковых элементов, этот элемент или один и тот же элемент, встречающийся более одного раза, является возможным элементом большинства. Вектор должен быть повторно просканирован, чтобы увидеть, встречается ли этот элемент более чем в два раза меньше общего количества элементов в векторе. Если он встречается более половины раз, то этот элемент является мажоритарным (ведущим); в противном случае вектор (или массив) не имеет мажоритарного элемента (функция должна возвращать −1).
Кодирование на С++
Всякий раз, когда вектор используется в программе на C++, заголовок программы должен быть примерно таким:
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
Библиотека стека должна быть включена. Используется стандартное пространство имен. Vector является основным списком, поэтому его библиотека включена. Библиотека iostream всегда должна быть включена; он отвечает за ввод/вывод. Имя функции для алгоритма O(n) — majorElement. Первая половина кода функции:
int majorityElement (vector<int> &A) {
int N = A.size();
int size = 0;
stack<int> st;
st.push(A[0]);for (int i=1; i<N; i++) {
if (st.size() > 0) { //to avoid, Segmentation fault (core dumped) error
if (A[i] == st.top()) {
st.push(A[i]);
}
else {
st.pop(); //if different
}
}
else {
st.push(A[i]); //push to top of stack if empty
}
}
Это первый цикл for, который является основным циклом for. Перед циклом for первый элемент вектора отправляется в стек (на вершину). Этот цикл for реализует упомянутую выше стратегию C++. Вторая и последняя часть функции mostElement():
int candidate = -1;
if (st.size() > 0)
candidate = st.top();
int leader = -1;
int count = 0;
for (int i=0; i<N; i++) {
if (A[i] == candidate) {
count += 1;
}
}
if (count > N/2)
leader = candidate;
return leader;
}
Это проверяет, действительно ли кандидат является мажоритарным элементом. Переменный лидер является синонимом мажоритарного элемента. Переменный кандидат является возможным элементом большинства. Как только значение count превышает N/2, кандидат становится мажоритарным элементом. В этой части есть цикл for, который проверяет, имеет ли вектор мажоритарный элемент. Вышеупомянутые две части должны быть объединены, чтобы сформировать одну функцию. Функция возвращает −1, если не существует мажоритарного элемента.
Подходящей основной функцией С++ для приведенного выше кода является:
{
vector<int> v1 = {6, 8, 4, 6, 8, 6, 6};
int ret1 = majorityElement(v1);
cout << ret1 << endl;vector<int> v2 = {3, 4, 3, 2, 3, —1, 3, 3};
int ret2 = majorityElement(v2);
cout << ret2 << endl;vector<int> v3 = {4, 3, 4, 4, 4, 2};
int ret3 = majorityElement(v3);
cout << ret3 << endl;vector<int> v4 = {5, 4, 7, 1, 7, 2, 3, 7, 8};
int ret4 = majorityElement(v4);
cout << ret4 << endl;return 0;
}
Сложность времени
Поскольку есть два цикла for с двукратным сканированием вектора, у читателя может возникнуть соблазн сказать, что временная сложность равна O(n+n). Теперь тело первого цикла for намного длиннее тела второго цикла for. Таким образом, время выполнения второго тела цикла for намного меньше, чем время выполнения первого тела цикла for. Другими словами, это время для второго тела относительно ничтожно. Итак, временная сложность для приведенного выше алгоритма указана как:
O(n)
Временная сложность — это примерное количество основных операций для рассматриваемой функции.
Заключение
Общая стратегия поиска мажоритарного элемента за время O(n) состоит в многократном удалении пар различных элементов, начиная слева в заданном списке. Если в списке окончательно не осталось ни одного элемента, значит, нет основного элемента, и функция должна вернуть −1. Если остался один или несколько одинаковых элементов, необходимо проверить, встречается ли этот элемент в списке более половины раз. Этот элемент называется кандидатом. Если кандидат встречается в данном списке более половины раз, то кандидат является элементом большинства.
