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 встречаются по одному разу.

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

Можете ли вы найти все значения, которые встречаются более чем n / 3 раз, за время O(n) и используя O(1) дополнительной памяти?

Решение

Большинство превосходит по численности все остальные значения вместе взятые. Вычёркивайте пары разных значений, и некоторые его копии всегда останутся. Алгоритм голосования Бойера — Мура выполняет такое попарное сопоставление за один проход, используя одного кандидата и один счётчик, поэтому карта подсчётов не нужна.

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

Идея

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

Каждый поиск в среднем выполняется за 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 снова становится кандидатом. Один проход с двумя переменными требует 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, а затем запустить цикл с индекса 0. Первый элемент голосует дважды: для [1, 2, 2] итоговое значение счётчика равно 0, и вы возвращаете 1.

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

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

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

Можно ли найти элемент большинства с помощью сортировки?

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

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

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

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

Тест #1

Тест #2

Аргумент

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

Ожидаемый вывод