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

Question

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

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

Answer 1

Keep одно целое число для каждого бита, и увеличивать эту коллекцию соответственно для каждого целого числа в массиве.

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

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

Answer 2

Псевдокода (блокнот 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 3

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

Answer 4

Boyer and Moore's "Linear Time Majority Vote Algorithm" - спуститесь по массиву, поддерживая текущее предположение в ответ.

Answer 5

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

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 6

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

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

Answer 7

Обратите внимание, что если последовательность 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 

Answer 8

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

---

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

---

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

Итак, если вы подсчитаете количество некоторых элементов и вычтите количество всех остальных элементов и получите число 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 majority vote algorithm.