在log n时间从大型排序数组中查找所有唯一元素？

Question

我有一个非常大的排序数组.我如何计算或打印数组的所有独特元素？

假设我的数组是[2,3,3,3,4,6,6,7],那么输出应该是2,3,4,6,7

我知道在(复杂)时间做这件事.但是面试官让我在日志时间里这样做？可能吗？

Answer 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)如果所有都是独特的,那么比线性更糟糕.