在对数时间内从一个大的排序数组中查找所有唯一元素？

Question

我有一个非常大的已排序数组。如何计算或打印出数组中所有唯一元素？

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

我知道如何在O(n)时间内完成这个任务。但面试官要求我在O(log n)时间内完成？这可能吗？

- Aman Jagga

---

由于打印元素的复杂度为O（n），所以只有在您仅具有预定义数量的不同元素时（假设数组中有整数1到10），才应该这样做。 - George Nechifor

面试官并不要求使用(log n)数量级的操作来完成任务。他要求复杂度为(log n)，这意味着操作次数与(log n)成比例。例如，对于o(n)算法，如果100个元素需要100,000次操作，则200个元素需要200,000次操作。而对于o(log n)算法，如果100个元素需要100,000次操作，则200个元素需要100,150等。（忽略实际数字，它们只是指示性的） - Kaushik Lele

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)，比线性还要劣。

- Vikram Bhat

---

当我被问到同样的问题时，我的面试官对这个解决方案非常满意。 - Niklas B.

Answer 2

我想知道面试官如何在不至少选取每个元素的情况下计算数组[1,2,3,4,5]中的每个唯一元素。在这种情况下，您必须选择每个元素才能计算每个元素，并且这将在O(n)内完成。在我看来，如果没有对给定数组的其他要求，那么不可能获得O(log n)的复杂度。

- Flupp

---

数组已经排序，所以你不需要查看每个元素。 - perreal

你必须至少读取整个数组，因此下限为O(n)。 - piotrekg2

@perreal 你必须查看每个元素，例如这种情况（2,5,7,100），你如何判断？ - Pham Trung

我认为可以用M log N的时间复杂度完成，其中M是结果的大小。您可以通过运行多个二进制搜索来实现这一点。 - piotrekg2

@FilipeGonçalves 下一个更高的数字 - Niklas B.