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

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

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

---

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

---

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

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

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

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

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

Answer 8

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