Найти элемент, повторяющийся больше, чем n/2 раза

Ответ 1

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

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

Чтобы реализовать алгоритм, вы выполняете линейное сканирование по массиву и отслеживаете свое текущее предположение относительно того, что такое элемент большинства, а также количество раз, которое вы видели до сих пор. Первоначально это предположение undefined, а число повторов равно нулю. Когда вы проходите через массив, если текущий элемент соответствует вашей предпосылке, вы увеличиваете счетчик. Если текущий элемент не соответствует вашей догадки, вы уменьшаете счетчик. Если счетчик когда-либо достигает нуля, вы reset его следующему элементу, с которым вы сталкиваетесь. Вы можете думать об этой реализации как о конкретной реализации вышеперечисленного алгоритма "стоять в комнате". Каждый раз, когда два человека встречаются с разными элементами, они отменяются (сбрасывая счетчик). Каждый раз, когда два человека имеют один и тот же элемент, они не взаимодействуют друг с другом.

Для полного доказательства корректности, ссылаясь на оригинальную статью (Бойер и Мур из более известного алгоритма соответствия строк Бойер-Мура) и реализацию на С++, проверьте приведенную выше ссылку.

Ответ 2

Это проблема элемента большинства. Для этой проблемы существует алгоритм с одним проходом, постоянным пространством. Вот краткий алгоритм, закодированный в python:

    import random

    items = [1, 2, 3, 4, 5, 5, 5, 5, 5 ]
    # shuffle the items
    random.shuffle(items)

    print("shuffled items: ", items)

    majority_elem = items[0]
    count = 1
    for i in range(1,len(items)):
        if items[i] == majority_elem:
            count += 1
        else: 
            count -= 1
            if count == 0:
                majority_elem = items[i]
                count = 1

    print("majority element : %d" % majority_elem )

  

Мы используем переменную most_elem для отслеживания элемента большинства и счетчика (счетчика)

• Сначала мы устанавливаем первый элемент массива как элемент большинства.

• мы перемещаемся по массиву,

• если текущий элемент == элемент: инкремент count

• else: {количество декрементов. если count становится равным нулю, установите count = 1 и установите для параметра most_element = current. }

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

Литература:

• Искусство компьютерного программирования, Fascicle 0: Введение в комбинаторные алгоритмы и булевы функции, том 0; Том 4

Ответ 3

Вы знакомы с quicksort? Он имеет функцию под названием "раздел", которая, учитывая значение, делит массив на секцию, где все значения больше, чем значение (ось поворота) находятся на одной стороне, тогда как все значения, меньшие значения, находятся на другой стороне. Обратите внимание, что это не сорт, просто разделение. Элемент счетчика N/2 будет находиться в большем из двух разделов. Вы можете рекурсивно применить эту технику, чтобы найти элемент в O (n) времени.

wikipedia: quicksort или алгоритм общего выбора на основе раздела

Ответ 4

В вашем втором подходе вы по существу выбираете медианный элемент. Взгляните на алгоритмы поиска медианы списка чисел. В частности, алгоритм будет отлично работать для этого и вычислить его в O (n).

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

В С++ стандартная библиотека предоставляет алгоритм выбора в виде std::nth_element, что гарантирует среднюю сложность O (n). Вы можете использовать эту медитацию.

int a[8] = {5, 1, 1, 1, 2, 1, 3, 1};
int median = *std::nth_element(a, a + 4, a + 8);

Обратите внимание, что std::nth_element также частично сортирует массив на месте.

Ответ 5

Если элемент повторяется более N/2 раза, то он должен быть медианным. Существуют многие алгоритмы, которые позволяют вам находить это эффективно.

Ответ 6

Не нужно сортировать. Вы можете просто использовать медианный алгоритм выбора для определения n/2-го элемента. Quickselect запускается в ожидаемое время O (n). Медиана медианов проходит в O (n).

Ответ 7

Сортировка массива с использованием любого алгоритма сортировки. Элемент, который повторялся более половины времени, всегда будет средним элементом. Сложность будет nlog (n).