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

Question

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

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

Answer 1

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

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

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

Answer 2

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

Answer 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.Я не проверял этот код — используйте его на свой страх и риск.

Answer 4

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

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);

Answer 5

Обратите внимание, что если последовательность a0, a1,. , , , & # 8722; 1 содержит лидера, затем после удаления пары элементы разных значений, оставшаяся последовательность по-прежнему имеет того же лидера. Действительно, если мы удалите два разных элемента, тогда только один из них может быть лидером. Лидер в новая последовательность встречается более чем n / 2 & # 8722; 1 = (n & # 8722; 2) / 2 раз. Следовательно, он по-прежнему является лидером новая последовательность n & # 8722; 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

Answer 6

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

<Ч>

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

<Ч>

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

Таким образом, если вы посчитаете количество какого-либо элемента, вычтете число всех других элементов и получите число 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 в длинную строку, и это количество элементов в массиве невообразимо велико.

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

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

Answer 7

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

Answer 8

Подтверждение правильности ответа бути-окса / Джейсона Эрнандеса, предполагая, что ответ Джейсона совпадает с ответом бути-оксы, и оба работают так, как должен работать описанный алгоритм:

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