数组中不同元素的数目

这是 Element uniqueness problem ,其下限为 Ω( n log n ) ,用于基于比较的模型。显而易见的散列或桶排序解决方案也都需要线性空间,所以我不确定这是否可行。

不能使用常量空间。您可以使用O(不同元素的数量)空间;这就是哈希集所做的。

您可以使用任何排序算法并计算数组中不同相邻元素的数量。

我认为这不可能在线性时间内完成。在O(n logn)中求解的一个算法需要首先对数组进行排序(然后比较变得微不足道)。

如果你保证数组中的数字在上面和下面是有界的,比如A和B,那么你可以分配一个大小为B-A的数组,并使用它来跟踪哪些数字已经被看到。

也就是说,您将在输入数组中移动,获取每个数字,并在目标数组中的该点标记为真。只有在遇到存储阵列中位置为假的数字时,才会增加一个不同数字的计数器。

假设我们可以部分破坏输入,这里有一个O(log n)位的n个字的算法。

通过线性时间选择,找到序列sqrt(n)的元素。使用此元素作为透视(o(n))对数组进行分区。使用蛮力,计算长度sqrt(n)分区中不同元素的数量。(这是o(sqrt(n)^2)=o(n)。现在在其余部分使用就地基数排序,其中每个“数字”是log(sqrt(n))=log(n)/2位,我们使用第一个分区存储数字计数。

如果只考虑流算法( http://en.wikipedia.org/wiki/Streaming_algorithm ,那么就不可能通过通信复杂度的下限,用存储的O(n)位得到准确的答案。( http://en.wikipedia.org/wiki/Communication_complexity ,但可以使用随机性和小空间(alon、matias和szegedy)来近似回答。

这可以用bucket方法来实现,前提是不同的值只有一个常量。为每个值制作一个标志(仍为常量空间)。遍历列表并标记发生的值。如果您碰巧标记了一个已标记的值,则会发现一个重复值。您必须遍历列表中每个元素的bucket。但这仍然是线性时间。