Метод с использованием алгоритма большинства голосов Бойера — Мура.
Алгоритм линейный, используется обычно для нахождения доминирующего элемента с количеством не менее длины половины массива. Очередной элемент старается вытеснить текущего лидера, если он с ним не совпадает, либо укрепляет его позицию, если совпадает. В конце остаётся элемент с count>=len/2
, если такой есть. А если такого нет - в лидерах остаётся произвольный, поэтому, к сожалению, нужен второй проход для подсчёта.
(Иначе для данной задачи можно было бы сравнивать с == len-2
, но это провалится на наборах типа [1,2,3]
)
Код на Python (тест на ideone):
def checku(a):
c = 0
for v in a:
if c == 0:
m = v
c = 1
else:
c = c + (1 if m == v else -1)
return a.count(m) == len(a) - 1
print(checku([1, 2]))
print(checku([1, 1, 2, 1, 1]))
print(checku([2, 1, 1, 1, 1]))
print(checku([1]))
print(checku([1, 2, 3]))
print(checku([1, 1, 2, 5, 1, 1]))
print(checku([1, 1, 1, 1, 1]))
print(checku([1, 1, 2, 2, 1]))
Перевод на js:
var print = console.log;
function checku(a) {
var c = 0
for (var v of a)
if (c == 0) {
var m = v;
c = 1;
} else {
c = c + (m == v ? 1 : -1);
}
return a.filter(el => m == el) == a.length - 1;
}
print(checku([1, 2]))
print(checku([1, 1, 2, 1, 1]))
print(checku([2, 1, 1, 1, 1]))
print(checku([1]))
print(checku([1, 2, 3]))
print(checku([1, 1, 2, 5, 1, 1]))
print(checku([1, 1, 1, 1, 1]))
print(checku([1, 1, 2, 2, 1]))
нового участника
: Необходимо Выбрать ответ, который вам больше всего подошёл и отметить его, как решение (галочка ниже цифры у ответа) Желательно также поблагодарить отвечающихupvote
(верхний серый треугольник)