为什么我的算法 O(1) 额外 space 复杂度？

Question

我通过 codefights 解决了这个问题：

注意：编写一个时间复杂度为 O(n) 且额外 space 复杂度为 O(1) 的解决方案，因为这是您在真实面试中会被要求做的事情。

给定一个仅包含 1 到 a.length 范围内的数字的数组 a，找到第一个重复数字，其中第二次出现的数字具有最小索引。换句话说，如果有超过 1 个重复的数字，return 第二次出现的数字的索引小于另一个数字的第二次出现的索引。如果没有这样的元素，return -1.

int firstDuplicate(int[] a) {
    HashSet z = new HashSet();
    for (int i: a) {
        if (z.contains(i)){
            return i;
        }
        z.add(i);
    }
    return -1;
}

我的解决方案通过了所有测试。但是我不明白我的解决方案如何满足 O(1) 额外的 space 复杂性要求。哈希表的大小与输入成正比，所以我认为它是 O(n) space 复杂度。 codefights 是否错误地测试了我的算法，还是我误解了什么？

Answer 1

这在技术上是不正确的，原因有二。

首先，根据数组中的值，当 int 变为 Integer 并添加到 HashSet 时可能会有开销。

其次，虽然额外的内存主要是与 HashSet 相关的开销，但该开销与集合的大小成线性比例。（请注意，我没有计算其中的元素，因为它们已经存在于数组中。）

通常，这些内存限制是通过设置它可以使用的内存量限制来测试的。我希望像这样的解决方案低于上述阈值。

Answer 2

您的代码没有 O(1) 辅助 space 复杂度，因为如果给定一个包含所有不同元素的数组，该哈希集可以增长到大小 n。

我的猜测是在线测试基础设施没有检查内存使用情况，或者检查内存使用情况不正确。如果您想满足 space 限制，则需要返回并尝试以不同的方式解决问题。

作为提示，考虑重新排序数组元素。

Answer 3

如果您能够修改输入数组，您可以使用 O(n) 时间复杂度解决问题，并且不要使用外部存储器.

public static int getFirstDuplicate(int... arr) {
    for (int i = 0; i < arr.length; i++) {
        int val = Math.abs(arr[i]);

        if (arr[val - 1] < 0)
            return val;
        arr[val - 1] = -arr[val - 1];
    }

    return -1;
}

为什么我的算法 O(1) 额外 space 复杂度？

Why is my algorithm O(1) additional space complexity?

java

algorithm

space-complexity