Java

Question

代码的space复杂度是多少？

我认为它是 O(1)，因为我在技术上没有将所有输入存储到一个数组中，所以我将它分成 2 个数组。

这段代码应该获取一个有重复项的数组，并找出两个没有重复项的数字。

我的代码：

public int[] singleNumber(int[] nums) {
        int[] res = new int[2];
        HashSet<Integer> temp = new HashSet<>();
        HashSet<Integer> temp2 = new HashSet<>();

        for (int i : nums) {
            if (!temp.contains(i)) temp.add(i);
            else temp2.add(i);
        }

        for (int i : nums) {
            if (!temp2.contains(i)) {
                if (res[0] == 0) res[0] = i;
                else res[1] = i;
            }
        }

        return res;
    }

Answer 1

space 复杂度为 "best case" O(1) 和 "worst-case" O(N)。最好的情况是 nums 中的所有数字都相同，最坏的情况发生在各种情况下......包括接近 N/2 重复的情况，这是你的预期用途 -案例.

所有情况下的时间复杂度都是O(N)。

这是我的推理。

时间复杂度。

假设hash函数是良性的，那么HashSet.add和HashSet.contains的时间复杂度都是O(1).

Integer.valueOf(int)的时间复杂度也是O(1)。

这些O(1)操作在两个O(N)循环中最多执行"some constant"次，使得整个计算及时O(N)。

Space 复杂度。

这有点复杂，但让我们只考虑所有 int 值都是唯一的最坏情况。这个说法

        if (!temp.contains(i)) temp.add(i);
        else temp2.add(i);

将把 Integer.valueOf(i) 添加到 temp 或 temp2。在这种特殊情况下，它们都将以 temp 结束。（想一想......）所以这意味着我们最终在 temp 集合中有 N unique 个条目，在 temp2 集合中有 none设置。

现在 HashSet 和 N 个条目所需的 space 是 O(N)。（比例常数很大......但是我们在这里谈论space 复杂性所以这不相关。）

最好的情况是所有 int 值都相同。然后你最终在 temp 中有一个条目，在 temp2 中有一个条目。（相同的值被重复添加到 temp2 集合中……什么都不做。）两个映射的 space 用法是 O(1).

但是（我听到你问）Integer.valueOf(int) 创建的对象呢？我认为他们不算数：

除非它们可以访问（通过 HashSet 对象之一），否则 Integer 对象将被垃圾收集。因此，它们不算作 space usage，因为它通常被认为是 in Java¹.
一个聪明的编译器实际上可以完全优化掉对 Integer 对象的需求。（不是当前一代的 HotSpot Java 编译器，但将来我们可以在生产编译器中看到这样的东西。）

^{1 - 如果您开始将临时（即立即无法访问）Java 对象视为 space 利用率并总结该利用率，您将得到毫无意义的结果；例如O(N^2) "space utilization" 的应用程序在 O(N) 大小的堆中运行。临时对象 do 计数，但仅当它们可访问时。在您的示例中，贡献是 O(1).}

Java - Space 此代码的复杂度

Java - Space complexity of this code

space-complexity

时间复杂度。

Space 复杂度。