16

面试的时候遇到这个问题，没法回答。您必须在数组中找到第一个唯一元素（整数）。例如：

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

然后独特的元素是1, 5, 7和第一个独特的1。

所需解决方案：

O(n) 时间复杂度。

O(1) 空间复杂度。

我试着说：

使用 Hashmaps、Bitvector……但它们都没有空间复杂度 O(1)。

谁能告诉我空间 O(1) 的解决方案？

4

4 回答 4

10

这是不可能的非严格证明：众所周知，当您使用 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 因为我们想要多次出现的元素。

于 2013-02-24T00:44:42.457 回答
0

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

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

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

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

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

如果有人找到解决方案，我将删除此答案，我欢迎任何关于将其变成更严格证明的指示。

于 2013-02-23T22:48:20.163 回答
0

注意：这在一般情况下不起作用。请参阅下面的推理。

创见

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

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

所以你向后构建堆，从数组中的最后一个元素开始，并将最后一个位置作为根。构建堆时，跟踪最近的非重复项。

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

假设上述情况属实，那么当您完成堆构建时，您就会知道哪个项目是第一个非重复项目。

为什么它不起作用

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

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

于 2013-02-23T23:19:03.497 回答
0

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 的数字

于 2017-06-27T01:47:15.967 回答