查找第一个独特的元素

Question

我在面试中遇到了一个问题，我无法回答。

你需要在数组中找到第一个唯一的元素（整数）。

例如：

3,2,1,4,4,5,6,6,7,3,2,3

唯一的元素是1, 5, 7，其中第一个唯一的元素是1。

所需解决方案:

O(n)时间复杂度。

O(1)空间复杂度。

我尝试使用哈希表、位向量等方法，但它们都没有O(1)的空间复杂度。

有人能告诉我空间复杂度为O(1)的解决方案吗？

- Anup Buchke

---

元素是否总是一起出现？ - smk

如果您可以修改输入数组呢？那么最多需要 O(n) 的空间，但有一些奇怪的限制 :) - Andrew Mao

我开始觉得这是不可能的，即使你可以洗牌输入。 - John Dvorak

@Jon：澄清一下，O(n)中没有比较排序。关于基数排序和计数排序，我假设如果有一种方法可以实现这一点，它将涉及到向后遍历数组并进行修改。 - Andrew Mao

我认为原帖的作者可能忘记了一些条件。如果有可能，这个问题早就已经解决了。现在只是在思考一个不可能性证明…… - Andrew Mao

Answer 1

这是一个非严谨的证明，它说明了不可能做到： 众所周知，如果使用O(1)空间，则重复检测不能比O(n*log n)更好。假设当前问题可以在O(n)时间和O(1)内存中解决。如果我们得到第一个非重复数字的索引'k'，而它不是0，那么我们就知道k-1是重复的，因此通过对数组进行一次额外的遍历，我们就可以找到它的副本，使得重复检测成为一个O(n)的练习。

再次强调，这并不是严格的证明，我们可以进入最坏情况分析，其中k始终为0。但它可以帮助你思考并说服面试官，说明这不太可能实现。 http://en.wikipedia.org/wiki/Element_distinctness_problem称： 在大小为n的多重集合中出现超过n/k次的元素可以在O(n log k)的时间内找到。这里k=n，因为我们要找到出现多次的元素。

- user1952500

---

+1，好的 - 你可以加上一个参考链接来证明O(n)时间复杂度，O(1)空间复杂度的重复检测是不可能的吗？ - us2012

我找不到原论文的链接(曾在研究生课程中学习过它)。在http://en.wikipedia.org/wiki/Element_distinctness_problem上有有趣的信息。 - user1952500

Answer 2

OP的问题原始版本没有提到数字的限制（尽管后来添加的数字可以是负数/正数/零）。在这里，我假设还有一个条件：

数组中的数字都比数组长度小且非负。

那么，给出一个O(n)时间，O(1)空间的解决方案是可能的，而且似乎是一道面试题，而且OP在问题中给出的测试用例符合上述假设。

解决方案：

for (int i = 0; i < nums.length; i++) {
  if (nums[i] != i) {
    if (nums[i] == -1) continue;
      if (nums[nums[i]] == nums[i]) {
        nums[nums[i]] = -1;
      } else {
        swap(nums, nums[i], i);
        i--;
      }
    }
  }
}

for (int i = 0; i < nums.length; i++) {
  if (nums[i] == i) {
    return i;
  }
} 

这里的算法将原始数组视为桶排序中的桶。将数字放入其桶中，如果超过两次，则将其标记为-1。使用另一个循环来查找第一个满足 nums[i] == i 的数字。

- Luke

Answer 3

注意：这种方法并不适用于所有情况。请参见下面的推理。

原始想法

也许有一种O(n)时间和O(1)额外空间的解决方案。

可以在O(n)时间内构建堆。请参见构建堆。

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

这假设在将项目插入堆时，您会遇到已经存在于堆中的任何相同项目。我不知道我能否证明这一点……

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

为什么它行不通

构建就地堆的算法从数组中点开始，并假定该点之后的所有节点都是叶节点。然后它向后工作（朝向项0），将项筛选到堆中。该算法不按特定顺序检查任何最后n/2个项，而且随着项被筛入堆中，顺序会发生变化。

因此，我们最好能做的事情（即使这样我也不确定我们能够可靠地做到这一点）就是仅在数组的前半部分出现第一个未重复的项。

- Jim Mischel

---

我很期待看到证明。 - John Dvorak

@us2012：我的措辞不太恰当。我应该说，“如果堆中存在相同的项，则返回一个相同的项。”无论如何，请查看我的更新，了解为什么这在一般情况下行不通。 - Jim Mischel

@DanielBrückner：你说得对：如果有无限的RAM，那么这个问题就很简单了。让我们把它限制在现实世界中吧。你有一个包含100,000,000个64位整数的数组。你的计算机只有1GB的RAM，没有外部存储器（操作系统是从ROM引导的）。请用O(n)时间复杂度和O(1)额外空间解决这个问题。 - Jim Mischel

假设（min）堆以1为根节点，2为左子节点且没有其他节点。现在要插入2。你会将它插入到堆的末尾，然后尝试将其向上筛选，但由于它已经在正确的位置，所以不会移动。并没有意识到它的兄弟节点也是2。 - naitoon

@naitoon：堆构建算法并不完全是这样工作的，但你的观察本质上仍然是正确的。给定数组[2,2,1]，该算法将构建堆[1,2,2]，而不会比较两个值为2的元素。 - Jim Mischel

Answer 4

我认为这是不可能的。这不是一个证明，而是一个猜想的证据。我的推理如下...

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

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

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

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

如果有人找到解决方案，我会删除这个答案，并欢迎任何关于将其转化为更严谨证明的指针。

- Andrew Mao

---

我们不能在数组中交换值，因为这样会导致独特值的原始顺序丢失。-- 我认为这是有争议的。 - John Dvorak

你只需要进行O(n)次比较来证明第一个元素是唯一的。 - John Dvorak

@G.Bach，“O(n^2)”比较显然足够。但你仍需要证明它们对于任何算法都是必要的。 - John Dvorak

不需要改变数组中存储的值的顺序，也不需要在最坏情况下为数组中的O(n)个不同值存储O(n)个信息，在不干扰原意的前提下，O(n^2)比较的上界是紧密的。只需取一组两两不同的值S，并将它们放入奇数长度的数组的前floor(n/2)个位置，然后在位置floor(n/2)+1上放一个唯一的值k，最后用S的随机排列填充数组的其余部分。需要O(n^2)次比较才能看到数组中的每个S中的值都是重复的。 - G. Bach

脑海中浮现出几个想法：使用某种直方图/哈希结构/等等来存储有关已读取哪些值的信息 -> 最坏情况下需要O(n)空间，对于O(n)不同的值。预先对数组进行排序 -> 对于无界值需要Omega(n log n)，并且扭曲了原始数组中独特值出现的顺序。想不出其他办法了。 - G. Bach