Задача: я хочу написать алгоритм, который бы находил мажоритарный элемент массива (или находил его отсутствие). По сути, я взял алгоритм с
LeetCode - Approach 5. Вот так выглядит мой код:
long long majority_element(vector<long long>& a, unsigned long long lo, unsigned long long hi) {
if (lo == hi) return a[hi];
auto mid = (hi - lo) / 2 + lo;
auto left = majority_element(a, lo, mid);
auto right = majority_element(a, mid+1, hi);
if (left == right) return right;
auto l_cnt = count(a.begin(), a.end(), left);
auto r_cnt = count(a.begin(), a.end(), right);
if (r_cnt == l_cnt) return 0; // если вернулся ноль - мажоритарного нет
return l_cnt > r_cnt ? left : right;
}
Я столкнулся с проблемой. Этот алгоритм, насколько я понимаю, исходит из того, что "если элемент мажоритарен в обоих половинах массива, он мажоритарен и в полном массиве". Если вдруг в разных частях разный мажоритарный элемент, конфликт легко решается пересчетом элементов во всем массиве с целью ответить на вопрос "Вхождений какого элемента больше?". Но, например, посмотрим на такой пример:
512766168 717383758 5 126144732 5 573799007 5 5 5 405079772
Очевидно, тут нет мажоритарного элемента. Но алгоритм разбивает исходный массив на две части и получает две половинки - и в каждой половинке 5 это мажоритарный элемент. И тогда, так как элемент мажоритарен в обоих сторонах массива, он мажоритарен и во всем массиве - возвращается 5, что, конечно, не верно. Можно ли как то пофиксить эту проблему без тупого count() в случае мажоритарности элемента в обоих половинках?
Простой