Поиск всех уникальных элементов из большого отсортированного массива за время журнала n?

#algorithm #time-complexity

#алгоритм #время-сложность

Вопрос:

У меня очень большой отсортированный массив. Как я могу посчитать или распечатать все уникальные элементы массива??

Предположим, что мой массив равен [2,3,3,3,4,6,6,7], тогда результат должен быть 2,3,4,6,7

Я знаю, как сделать это за n (сложность) времени. Но интервьюер попросил меня сделать это за время регистрации n?? Возможно ли это?

1. Поскольку печать элементов — это сложность O (n), этого не должно быть, если у вас есть только предопределенное количество разных элементов (предположим, у вас есть целые числа от 1 до 10 в массиве).

2. Интервьюер не просит выполнять задачу с (log n) количеством операций. Он просит, чтобы сложность была (log n), это означает, что количество операций пропорционально (log n). например, для алгоритма o (n), если для 100 элементов требуется 100 000 операций, то для 200 элементов потребуется 200 000 операций. где, что касается алгоритма o (log n), если для 100 элементов требуется 100 000 операций, то для 200 элементов потребуется 100 150 и т.д. (Игнорируйте фактические числа. Они просто ориентировочные)

Ответ №1:

Вот алгоритм, который требует O(logn*k) , чтобы где k — уникальные элементы:-

 set uniQ
int ind = 0;

do {

 uniQ.add(arr[i]);
 ind = BinSearchGreater(arr,arr[ind],ind 1);
 if(ind >= arr.length)
   break;

} while(true);


BinSearchGreater(arr,key,start_ind) : returns index of first element greater than key in subarray starting at start_ind

Временная сложность :-
Обратите внимание, что этот алгоритм хорош только тогда, когда ни один из уникальных элементов не является маленьким.
Это асимптотически O(n*logn) , если все уникальны, поэтому хуже, чем линейные.

Ответ №2:

Я хотел бы знать, как он (интервьюер) подсчитывает каждый уникальный элемент в массиве [1,2,3,4,5], не выбирая хотя бы каждый элемент. В этом случае вам нужно выбрать каждый элемент для подсчета каждого элемента, и это будет сделано за O (n) . На мой взгляд, невозможно получить сложность O (log n), если к данному массиву нет других требований.

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

2. Вы должны хотя бы прочитать весь этот массив, чтобы нижняя граница была O (n)

3. @perreal вы должны просмотреть каждый элемент, например, этот случай (2,5,7,100), как вы можете определить?

4. Я думаю, это можно сделать в M log N where M — размер результата. Вы можете добиться этого, выполнив несколько двоичных поисков.

5. @PhamTrung, это список всех элементов uniq, поэтому даже печать равна O (n). Что делать, если у вас есть логарифмические (n) уникальные элементы?