Majority Element

+10

Дан массив целых чисел nums длины n. Одно значение встречается в нём более n / 2 раз и называется элементом большинства. Верните его. Значение, занимающее более половины массива, всегда уникально, поэтому ответ ровно один.

Функция

majorityElement(nums: integer-array) → integer

numsinteger-array: массив целых чисел, в котором одно значение занимает больше половины элементов
Возвращаетinteger: значение, которое встречается более чем в n / 2 случаях

Ограничения

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
Одно значение встречается более чем nums.length / 2 раз.

Примеры

Ввод: nums = [3, 9, 3, 3, 4]
Вывод: 3
Пояснение: 3 встречается три раза среди пяти элементов. Три больше, чем 5 / 2 = 2.5, а 9 и 4 встречаются по одному разу.

+15 скрытых тестов при отправке

Дополнительный вопрос

Сможешь найти элемент большинства за время O(n), используя O(1) дополнительной памяти, не сортируя массив?

Решение

Подсчёт того, как часто встречается каждое значение, даёт ответ на вопрос, но для подсчётов нужна хеш-таблица. Чтобы обойтись без неё, посмотрим, что отличает большинство: его больше, чем всех остальных значений вместе взятых. Сопоставь каждую его копию с другим значением и вычеркни обе — некоторые копии всегда останутся. Алгоритм голосования Бойера — Мура выполняет такое сопоставление за один проход с помощью одного кандидата и одного счётчика.

Подсчёт с помощью хеш-таблицы

Идея

Пройди по массиву и храни в хеш-таблице для каждого значения количество раз, которое ты его встретил. После того как увеличишь счётчик значения на единицу, проверь, стало ли это количество больше половины длины массива. Первое значение, которое превысит эту границу, и будет большинством, поэтому можешь сразу его вернуть.

Для [3, 9, 3, 3, 4] счётчик числа 3 становится равным 1 на индексе 0, 2 — на индексе 2 и 3 — на индексе 3. Три вхождения из пяти — это больше 2.5, поэтому ты возвращаешь 3, не читая последний элемент.

Поиск и обновление в хеш-таблице в среднем занимают O(1), поэтому время работы составляет O(n). В таблице может храниться до примерно n / 2 различных значений, поэтому дополнительная память составляет O(n). Следующий подход позволяет обойтись без таблицы.

Алгоритм

Создайте пустое отображение значений на их количество.
Для каждого элемента x увеличивайте количество x на 1.
Если это количество, умноженное на 2, больше длины массива, верните x.

def majorityElement(nums):
    counts = {}
    for x in nums:
        counts[x] = counts.get(x, 0) + 1
        if counts[x] * 2 > len(nums):
            return x

Голосование Бойера — Мура

Идея

Представь массив как выборы. Выбери одного candidate и отслеживай count его голосов, которые ещё никто не отменил. Элемент, равный кандидату, добавляет голос. Отличающийся элемент отменяет один голос, и оба элемента вместе выбывают из гонки. Когда счётчик равен 0, следующий элемент становится новым кандидатом.

Почему оставшееся в конце значение — это большинство: при каждой отмене удаляются два разных значения, поэтому удаляется не больше одной копии большинства. Пусть большинство встречается m раз. Других элементов всего n - m, то есть меньше, чем m, поэтому они не могут отменить все копии. Все голоса, оставшиеся в конце, принадлежат последнему кандидату, и среди них есть копия большинства, значит, кандидат и есть большинство.

Для массива [8, 8, 1, 1, 8, 1, 8] счётчик принимает значения 1, 2, 1, 0: две единицы отменили обе восьмёрки. Следующая 8 начинает новый отсчёт со счётчиком 1, следующая 1 отменяет её, а последняя 8 снова становится кандидатом. В результате ты получишь 8. Один проход с двумя переменными занимает O(n) времени и O(1) памяти.

Алгоритм

Присвойте candidate значение первого элемента, а count — значение 0.
Для каждого элемента x, если count равен 0, сделайте x кандидатом.
Если x равен кандидату, увеличьте count на 1. В противном случае уменьшите на 1.
После последнего элемента верните candidate.

def majorityElement(nums):
    candidate = nums[0]
    count = 0
    for x in nums:
        if count == 0:
            candidate = x  # the old candidate's votes are used up
        if x == candidate:
            count += 1
        else:
            count -= 1  # x and one copy of the candidate cancel out
    return candidate

Ловушки и крайние случаи

Большинство неправильных ответов связано с неверным пониманием условия «больше половины» или с чрезмерной трактовкой счётчика.

«Больше половины» означает строго больше. count >= n / 2 принимает 2 копии из 4, а это не большинство. Сравните с count * 2 > n — так округление не помешает.
Итоговое значение count в алгоритме Бойера — Мура не показывает, сколько раз встречается большинство. Для [8, 8, 1, 1, 8, 1, 8] оно заканчивается на 1, хотя 8 встречается четыре раза.
Начинать с candidate = nums[0] и count = 1 правильно, только если затем цикл начинается с индекса 1. Если начать его с индекса 0, первый элемент проголосует дважды: на входных данных [1, 2, 2] счётчик в итоге будет равен 0, и вы вернёте 1.
Алгоритм Бойера — Мура полагается на гарантию наличия большинства. На входных данных [1, 2, 3], в которых большинства нет, он всё равно возвращает 3. Если большинство может отсутствовать, посчитайте количество вхождений кандидата во втором проходе, прежде чем считать его правильным ответом.

Частые вопросы4

Что такое алгоритм голосования Бойера — Мура?

Он находит значение, которое встречается более чем в половине элементов списка, за один проход и с использованием O(1) памяти. Он хранит кандидата и счётчик: совпадающий элемент увеличивает счётчик на единицу, другой элемент уменьшает его на единицу, а при значении 0 следующий элемент становится кандидатом. Поскольку элементов со значением большинства больше, чем элементов со всеми остальными значениями вместе взятыми, в конце остаётся именно оно.

Какова временная и пространственная сложность задачи «Элемент большинства»?

Алгоритм голосования Бойера — Мура работает за время O(n) и использует O(1) дополнительной памяти. Подсчёт с помощью хеш-таблицы также занимает время O(n), но требует O(n) памяти для хранения счётчиков. Сначала выполнить сортировку — значит потратить время O(n log n).

Можно ли решить задачу Majority Element с помощью сортировки?

Да. После сортировки все копии большинства находятся в одном блоке длиной больше половины массива, и любой такой блок охватывает среднюю позицию. Поэтому элемент с индексом n / 2, округлённым вниз, и есть ответ. Его коротко записать, но это требует времени O(n log n).

Что, если в массиве может не быть элемента, встречающегося чаще остальных?

Алгоритм Бойера—Мура всегда возвращает некоторый кандидат, даже если ни одно значение не встречается более чем в половине массива. Добавь второй проход, который подсчитывает количество вхождений кандидата, и принимай его только в том случае, если это количество больше n / 2. Общая сложность остаётся O(n) по времени и O(1) по памяти.

Python

def majorityElement(nums):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Ввод

nums = [3, 9, 3, 3, 4]

Ожидается