В этой статье мы обсудим интересное решение, казалось бы, простой проблемы - проблемы Элемент большинства.

Постановка проблемы:

Для несортированного массива размером n найдите элемент большинства, если он существует. Элемент большинства - это элемент, который встречается более ⌊ n / 2 ⌋ раз.

Чтобы лучше понять проблему - если массив имеет размер 4, элемент, который встречается более двух раз, будет считаться элементом большинства, а если массив имеет размер 7, элемент, который встречается более трех раз, будет считаться элементом большинства. .

Пример тестового случая:

Дано: несортированный целочисленный массив -

[ 5, 10, 3, 2, 3, 3, 3, 1, 3, 3, 3, 4]

Ожидаемый результат:

3

(В приведенном выше примере 3 является основным элементом в массиве, поскольку он встречается всего 7 раз в массиве размером 12. (7 ›⌊ 12/2 ⌋)

Подходы к решению:

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

  1. Наивным решением могло бы быть выполнение цикла по массиву для каждого элемента, чтобы проверить, появляется ли он более ⌊ n / 2 ⌋ раз. Но это имеет временную сложность O (n²), и существует лучшее решение.
  2. Лучшее решение будет включать сортировку массива, чтобы все вхождения отображались рядом, так что теперь мы можем проверить, размещается ли какое-либо из них последовательно более ⌊ n / 2 ⌋ раз. У этого есть лучшая временная сложность, чем потребность во вспомогательном пространстве O (nlogn) и O (1). Неплохая идея, но мы можем сделать лучше.
  3. Другой подход может заключаться в использовании карты для хранения частоты появления элементов, чтобы определить, превышает ли какая-либо из их частот ⌊ n / 2 ⌋. Несмотря на то, что это работает во время O (n), для этого требуется вспомогательное пространство O (n). Существует даже лучшее решение этой проблемы, на которое мы будем фокусироваться.
  4. Подход, который мы собираемся обсудить, основан на алгоритме большинства голосов Бойера – Мура (если вы слышали о машинах Мура в теории вычислений, нет, это не тот же Мур). Это занимает O (n) времени и O (1) вспомогательного пространства.

Алгоритм большинства голосов Бойера – Мура:

Этот алгоритм можно разделить на две части -

  • В первой части мы ищем возможный элемент большинства.
  • Во второй части мы проверяем, действительно ли полученный элемент является элементом большинства.

(Вторая часть требуется только в том случае, если есть вероятность, что в массиве нет мажоритарного элемента. В версии LeetCode проблемы предполагается, что каждый массив имеет мажоритарный элемент, и поэтому в этом случае только первой части достаточно)

Часть 1. Поиск возможного элемента большинства:

Давайте сначала обсудим основную концепцию, из которой основан алгоритм.

Поскольку элемент большинства по определению встречается более n / 2 ⌋ раз, вхождение всех других элементов в суммированном массиве по-прежнему будет меньше n / 2 ⌋. Таким образом, обходя массив только один раз, мы можем указать, присутствие какого элемента перевешивает другие. Это достигается за счет того, что элементы «голосуют».

Алгоритм:

  • Инициализировать A [0] как мажоритарный элемент и инициализировать счетчик значением 0;
  • Просмотрите каждый элемент массива A и для каждого элемента выполните следующие действия:
  • если текущий элемент равен значению большинства, счетчик увеличения, в противном случае счетчик уменьшения;
  • если счетчик становится равным 0, повторно инициализируйте основной элемент как текущий элемент A [i], увеличивайте счетчик один раз и повторите.

Часть 2: Проверка нашего результата:

Эта часть довольно проста. Он просто обходит массив один раз, чтобы увидеть, действительно ли элемент, который мы пометили как Majority, встречался более ⌊ n / 2 ⌋ раз. Если нет, это просто означает, что в массиве нет большинства элементов, и мы возвращаем -1.

Подтверждение правильности:

Алгоритм большинства голосов Бойера – Мура может быть доказан с помощью математической индукции. (Вы можете пропустить эту часть, если вам нужно только общее представление)

Тривиальный случай: если длина массива = 1, единственным элементом массива является элемент большинства, и алгоритм голосования даст правильный ответ.

Для length = n: Предположим, что алгоритм дает правильные результаты для всех массивов длиной меньше или равной n. (Гипотеза 1)

Для длины m = n + 1: если мы сможем доказать, что алгоритм большинства голосов Бойера – Мура также применим для массивов длины m, по принципу математической индукции мы можем сказать, что он всегда будет возвращать большинство элемент, если он существует.

При выполнении могут возникнуть две ситуации:

  1. Счетчик никогда не опускается до нуля
  2. Счетчик падает до нуля во время итерации (мы будем называть это «точкой сброса»).

Ситуация 1. произойдет только в том случае, если первый элемент является основным элементом, и поэтому алгоритм всегда будет возвращать правильный ответ.

Если произойдет ситуация 2., у нас будет «точка сброса», где, как указывает название, состояние счетчика сбрасывается до нуля, и теперь он не знает, какой элемент может быть основным. Предположим, что эта точка сброса происходит на длине x от начала. Возможны два разных случая:

  • 2.a. Элемент большинства M не появился в подмассиве длиной x
  • 2.b. Элемент большинства M появился в подмассиве длиной x

2.a. Если M не появился в подмассиве, это означает, что все экземпляры M находятся в остальной части подмассива длины (m- x ), поэтому M является основным элементом следующей части массива. Поскольку (m- x) ≤ n, по нашей гипотезе этот алгоритм даст правильный ответ.

2.b. Если в подмассиве появилось M, оно могло появиться не более ⌊ x / 2⌋ раз, в противном случае счетчик определил бы M как большинство . Это означает, что в остальной части массива он появлялся как минимум (⌊m / 2⌋-⌊ x / 2⌋ + 1) раз. (Поскольку во всем массиве M встречается не менее (⌊m / 2⌋ + 1) раз.)

(⌊m/2⌋-⌊x/2⌋+1) = (⌊(m-x)/2⌋+1)

Следовательно, M по-прежнему составляет большинство в следующем подмассиве длины (m- x).

Опять же, поскольку (m- x) ≤ n, по нашей гипотезе этот алгоритм идентифицирует M как элемент большинства и все равно даст правильный ответ.

Таким образом, мы можем заключить, по принципу математической индукции, алгоритм большинства голосов Бойера – Мура во всех случаях возвращает элемент большинства.

Проработанный пример:

Давайте проведем пробный запуск и лучше поймем, как это работает:

Eg .

Input : [ 5, 10, 3, 2, 3, 3, 3, 1, 3, 3, 3, 4]

Output : 3

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

Надеюсь, вы нашли это полезным.

Удачного кодирования!