Найти наиболее распространенную запись в массиве

Вам предоставляется 32-разрядный целочисленный массив без знака с длиной до 2 ³² с тем свойством, что более половины записей в массиве равны N, для некоторых 32-разрядных unsigned integer N. Найдите N, просматривая каждое число в массиве только один раз и используя не более 2 Кбайт памяти.

Ваше решение должно быть детерминированным и гарантированно найти N.

Ответ 1

Сохраняйте одно целое число для каждого бита и соответствующим образом увеличивайте эту коллекцию для каждого целого в массиве.

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

(Нет кода в настоящий момент - вот-вот потеряет чистый доступ. Надеюсь, что это достаточно ясно, хотя.)

Ответ 2

Бойер и Мур "Алгоритм голосования большинства по времени" - спуститесь по массиву, поддерживая текущую догадку ответа.

Ответ 3

Вы можете сделать это только с двумя переменными.

public uint MostCommon(UInt32[] numberList)
{
    uint suspect = 0;
    int suspicionStrength = -1; 
    foreach (uint number in numberList)
    {
        if (number==suspect)
        {
            suspicionStrength++;
        }
        else
        {
            suspicionStrength--;
        }

        if (suspicionStrength<=0)
        {
            suspect = number;
        }
    }
    return suspect;
}

Сделайте первый номер подозрительным номером и продолжите цикл по списку. Если число соответствует, увеличьте силу подозрительности на единицу; если он не соответствует, опустите силу подозрительности на единицу. Если уровень подозрительности достигает 0, текущее число становится подозрительным. Это не сработает, чтобы найти наиболее распространенное число, только число, которое составляет более 50% группы. Сопротивляйтесь желанию добавить проверку, если suspicionStrength больше половины длины списка - это всегда приведет к более полному сравнению.

P.S. Я не тестировал этот код - используйте его на свой страх и риск.

Ответ 4

Псевдокод (блокнот С++:-)) для алгоритма Jon:

int lNumbers = (size_of(arrNumbers)/size_of(arrNumbers[0]);

for (int i = 0; i < lNumbers; i++)
  for (int bi = 0; bi < 32; bi++)
    arrBits[i] = arrBits[i] + (arrNumbers[i] & (1 << bi)) == (1 << bi) ? 1 : 0;

int N = 0;

for (int bc = 0; bc < 32; bc++)
  if (arrBits[bc] > lNumbers/2)
    N = N | (1 << bc);

Ответ 5

Обратите внимание, что если последовательность a0, a1, . . . , an−1 содержит лидера, то после удаления пары элементы разных значений, остальная последовательность по-прежнему имеет один и тот же лидер. Действительно, если мы удалить два разных элемента, тогда только один из них может быть лидером. Лидер в новая последовательность происходит больше, чем n/2 − 1= (n−2)/2 раз. Следовательно, он по-прежнему является лидером новая последовательность элементов n − 2.

Вот реализация Python с временной сложностью O (n):

def goldenLeader(A):
    n = len(A)
    size = 0
    for k in xrange(n):
        if (size == 0):
            size += 1
            value = A[k]
        else:
            if (value != A[k]):
                size -= 1
            else:
                size += 1
    candidate = -1
    if (size > 0):
        candidate = value
    leader = -1
    count = 0
    for k in xrange(n):
        if (A[k] == candidate):
            count += 1
    if (count > n // 2):
        leader = candidate
    return leader

Ответ 6

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

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

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

Итак, если вы подсчитаете количество некоторых элементов и вычтите количество всех других элементов и получите число 0, то ваш исходный элемент не может быть элементом большинства. Это, если основание для правильного алгоритма:

Имеют две переменные, счетчик и возможный элемент. Итерируйте поток, если счетчик равен 0 - вы перезаписываете возможный элемент и инициализируете счетчик, если номер совпадает с возможным элементом - увеличивайте счетчик, в противном случае уменьшите его. Код Python:

def majority_element(arr):
    counter, possible_element = 0, None
    for i in arr:
        if counter == 0:
            possible_element, counter = i, 1
        elif i == possible_element:
            counter += 1
        else:
            counter -= 1

    return possible_element

Ясно, что алгоритм O(n) с очень небольшой константой до O(n) (например, 3). Также похоже, что сложность пространства O(1), потому что у нас есть только три инициализируемые переменные. Проблема в том, что одна из этих переменных является счетчиком, который потенциально может вырасти до n (когда массив состоит из одинаковых чисел). И чтобы сохранить номер n, вам нужно O(log (n)) пробел. Таким образом, с теоретической точки зрения это время O(n) и O(log(n)). С практической вы можете поместить число 2 ^ 128 в longint, и это количество элементов в массиве невообразимо велико.

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

Канал истории: этот алгоритм был изобретен где-то в 1982 году Бойером Муром и назван алгоритм голосования большинства Boyer-Moore.

Ответ 7

У меня есть воспоминания об этом алгоритме, который может или не может следовать правилу 2K. Возможно, его нужно будет переписать с помощью стеков и т.п., Чтобы избежать нарушения ограничений памяти из-за вызовов функций, но это может быть ненужным, поскольку оно имеет только логарифмическое число таких вызовов. Во всяком случае, у меня есть смутные воспоминания из колледжа или рекурсивное решение этого вопроса, которое связано с делением и победой, причем секрет заключается в том, что когда вы разделяете группы пополам, по крайней мере одна из половинок все еще имеет более половины своих значений, равных max, Основное правило при делении заключается в том, что вы возвращаете два верхних значения кандидата, одним из которых является верхнее значение, а одно из них - какое-то другое значение (которое может быть или не быть 2-м). Я забыл сам алгоритм.

Ответ 8

Доказательство правильности для buti-oxa/Jason Hernandez ответ, предполагая, что ответ Джейсона такой же, как ответ на buti-oxa, и оба работают так, как должен работать описанный алгоритм:

Мы определяем скорректированную силу подозрительности как равную силе подозрительности, если выбрано верхнее значение или -suspicion strength, если верхнее значение не выбрано. Каждый раз, когда вы выбираете правильный номер, текущая корректировка силы подозрительности увеличивается на 1. Каждый раз, когда вы выбираете неправильный номер, он либо падает на 1, либо увеличивается на 1, в зависимости от того, выбран ли в данный момент неправильный номер. Таким образом, минимально возможная конечная скорректированная сила подозрительности равна числу [верхних значений] - числу [других значений]