问寻找第一唯一元素

EN

这里有一个非严格的证据证明这是不可能的:众所周知，当您使用O(1)空间时，重复检测不能优于O(n * log )。假设当前问题在O(n)时间和O(1)内存中是可解的。如果我们得到的第一个非重复数的指数'k‘不是0，我们就知道k-1是一个重复的，因此，再扫一次数组，我们就可以得到它的重复，使重复检测成为O(n)练习。

同样，它并不严格，我们可以进入最坏的情况分析，其中k总是0。但它帮助你思考并说服面试官，这是不可能的。

问题说:在一个大小为n的多个集合中出现超过n/k次数的元素可以在时间O(n log k)中找到。这里k=n，因为我们想要出现不止一次的元素。

我觉得这不可能。这不是证据，而是猜测的证据。我的推理如下..。

首先，您说过元素的值没有限制(它们可以是负的、0的，也可以是正的)。第二，只有O(1)空间，所以我们不能存储超过一个固定数量的值。因此，这意味着我们只能用比较来解决这个问题。此外，我们不能对数组中的值进行排序或交换，因为我们会丢失唯一值的原始排序(并且无法存储原始排序)。

考虑一个数组，其中所有整数都是唯一的：

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

为了在这个数组上返回正确的输出1，而不需要重新排序数组，我们需要将每个元素与所有其他元素进行比较，以确保它是唯一的，并以相反的顺序执行，因此我们可以最后检查第一个唯一元素。这需要O(n^2)与O(1)空间进行比较。

如果有人找到了解决方案，我会删除这个答案，我欢迎任何关于将这个问题变成更严格的证明的建议。

注意：在一般情况下是行不通的。请看下面的推理。

原始思想

也许在O(n)时间和O(1)额外空间中有一个解。

可以在O(n)时间内构建堆。见建立一个堆。

因此，您向后构建了堆，从数组中的最后一个元素开始，并使最后一个位置成为根。在构建堆时，要跟踪最近没有重复的项。

这假定在将项插入堆中时，您将遇到堆中已经存在的任何相同项。我不知道我能不能证明。。。

假设上面的内容是正确的，那么当您构建堆时，您知道哪个项是第一个非重复项。

，为什么它不能工作，

构建适当堆的算法从数组的中点开始，并假定超过该点的所有节点都是叶节点。然后，它向后工作(针对项0)，将项筛选到堆中。该算法不会以任何特定的顺序检查最后的n/2项，并且随着项被筛选到堆中，顺序也会发生变化。

因此，我们所能做的最好的事情(即使这样，我也不确定我们是否能够可靠地做到这一点)只有在数组的前半部分出现时，才能找到第一个不重复的项。