Редкие элементы в массивах

Question

Нам задан отсортированный массив A [1..n] из n целых чисел. Мы говорим, что элемент x E A встречается редко, если он встречается в A строго меньше, чем n/10 раз. То есть x редко встречается, если существует некоторый индекс 1 < = i < = n такой, что A (i) = x, и строго меньше n/10 различных индексов j, для которых A (j) = x. Наша цель состоит в том, чтобы найти редкий элемент или выход, который не содержит редких элементов.

Ввод: Сортированный массив A [1..n] из n целых чисел.

Выход: Редкий элемент х Е А, или выход «Нет редкий элемент не существует в А.»

Есть ли O (журнал п) алгоритм времени для задачи редкого элемента? Что это?

T (n) = 10 T (n/10) + O (1) дает время O (n), которое недостаточно для меня.

Answer 1

Да, это возможно сделать в O(log n). Я предполагаю, что у вас уже есть этот массив в памяти. В противном случае это невозможно сделать быстрее, чем в O(n), потому что вам нужно как минимум прочитать массив.

Предположим, что step - самое большое целое число, которое меньше n/10. Если step равно нулю, то у нас нет редких элементов.

Рассмотрим следующий алгоритм:

int start = 1; 
while (true) { 
    if (n - start + 1 <= step) { 
    OutputRare(A[start]); Exit; 
    } 
    int next_index = start + step; 
    if (A[start] != A[next_index]) { 
    OutputRare(A[start); Exit; 
    } 
    // Here we need to find the smallest index starting from start with 
    // element that is not equal to A[start]. If such element does not 
    // exist function returns -1. 
    next_index = FindFirstNonEqual(A[start], start); 
    if (next_index == -1) { 
    // There is no rare elements 
    Exit; 
    } 
    start = next_index; 
} 

Этот алгоритм возвращает либо редкоземельный элемент, или увеличивается начать, по крайней мере, step. Это означает, что он увеличит начало ~ 10 раз (потому что каждый шаг составляет около n/10). FindFirstNonEqual может быть реализован с использованием двоичного поиска, что означает, что общая сложность составляет O(10log n) = O(log n).