Как найти число, которое было повторено (n / 3) раз массив размером n, в O (n) времени и O (n) пространстве?

Question

У меня есть вопрос, который я просто не могу понять! Любые намеки будут много значить. Заранее спасибо. У меня есть массив, A. Его размер равен n, и я хочу найти алгоритм, который найдет x, который появляется в этом массиве по крайней мере n/3 раз. Если в массиве нет такого x, мы напечатаем, что не нашли ни одного! Мне нужно найти алгоритм, который делает это за O(n) времени и занимает O(n) пространства.

Например:

A=[1 1 2 2 1 1 1 5 6 7]

Для приведенного выше массива алгоритм должен вернуть 1.

Answer 1

На вашем месте я напишу алгоритм, который:

1. Создает карту (т. Е. Пары ключ / значение) на любом языке, который вы используете. Ключом будет целое число, которое вы найдете, а значением будет количество раз, которое оно было просмотрено.
2. Итерация по массиву. Для текущего целого числа проверьте, существует ли число в качестве ключа на вашей карте. Если он существует, увеличьте значение карты. Если он не существует, вставьте новый элемент со счетчиком 1.
3. После завершения итерации выполните итерацию по вашей карте. Если число элементов превышает n/3, распечатайте его. Обработать случай, когда ничего не найдено, et c.

Answer 2

Вот мое решение в псевдокоде; обратите внимание, что возможно иметь два решения, а также одно или ни одного:

func anna(A, n)                  # array and length
    ht := {}              # create empty hash table
    for k in [0,n)             # iterate over array
        if A[k] in ht             # previously seen
            ht{k} := ht{k} + 1    # increment count
        else                      # previously seen
            ht{k} := 1           # initialize count
    solved := False        # flag if solution found
    for k in keys(ht)     # iterate over hash table
        if ht{k} > n / 3           # found solution
            solved := True            # update flag
            print k                      # write it
    if not solved               # no solution found
        print "No solution"        # report failure

Первое for l oop занимает время O ( n ). Вторая for l oop потенциально занимает время O ( n ), если все элементы в массиве различны, хотя чаще всего вторая for l oop занимает намного меньше времени. Таблица ha sh занимает пространство O ( n ), если все элементы в массиве различны, хотя чаще всего это занимает гораздо меньше места.

Можно оптимизировать решение так, он останавливается рано и сообщает о сбое, если нет возможных решений. Чтобы сделать это, сохраните переменную max в первом for l oop, увеличивайте ее каждый раз, когда она будет превышена новым числом таблиц ha sh, и проверяйте после добавления каждого элемента в таблица ha sh, если max + n - k <<em> n / 3.