Блог

Это пример. Каждое число представляет собой значение в диапазоне между [0 ..k]. Говорят, что число x часто появляется в A, если по крайней мере 1/3 чисел в массиве равно x.

Каким был бы алгоритм O (n), который находил бы часто появляющиеся числа для случая, когда k на порядки больше, чем n?

Почему бы не использовать хэш-карту, то есть отображение (словарь) на основе хэша из целых чисел в целые числа? Затем просто выполните итерацию по вашему входному массиву и вычислите счетчики. В императивном псевдокоде:

 const int often = ceiling(n/3);
hashmap m;

for int i = 1 to n do {
    if m.contains(A[i])
       m[A[i]]  = 1;
    else 
       m[A[i]] = 1;

    if m[A[i]] >= often
        // A[i] is appearing often
        // print it or store it in the result set, etc.
}
 

Это O(n) с точки зрения времени (ожидаемого) и пространства.