这种情况下 bitset 的 space 复杂度是多少

Question

我正在做一个 leetcode 问题，我必须找到大小为 [1-N] 的数组的副本，并找到了这个解决方案：

    public int findDuplicate(int[] nums) {
        BitSet bit = new BitSet();
        for(int num : nums) {
            if(!bit.get(num)) {
                bit.set(num);
            } else {
                return num;
            }
        }
        return -1;
    }

我假设这里使用 bitset 类似于使用 boolean[] 来跟踪我们之前看到的当前数字。所以我的问题是 space 的复杂性是什么？运行时似乎是 O(n)，其中 n 是输入数组的大小。 space 复杂度也是如此吗？

Link 问题：https://leetcode.com/problems/find-the-duplicate-number/

Answer 1

您的 Bitset 创建了一个基础 long[] 来存储值。阅读 Bitset#set 的代码，我可以肯定地说数组永远不会大于 max(nums) / 64 * 2 = max(nums) / 32。由于 long 具有固定大小，因此归结为 O(max(nums))。如果 nums 包含较大的值，您可以使用散列映射做得更好。

我正在用简单的代码尝试这个，它似乎证实了我对代码的阅读。

BitSet bitSet = new BitSet();

bitSet.set(100);
System.out.println(bitSet.toLongArray().length); // 2 (max(nums) / 32 = 3.125)

bitSet.set(64000);
System.out.println(bitSet.toLongArray().length); // 1001 (max(nums) / 32 = 2000)

bitSet.set(100_000);
System.out.println(bitSet.toLongArray().length); // 1563 (max(nums) / 32 = 3125)

注意我加的2因子是保守的，一般来说它会是一个较小的因子，这就是为什么我的公式始终over-estimates长数组的实际长度，但从来没有超过比 2 倍。这是 Bitset 中的代码让我添加它：

private void ensureCapacity(int wordsRequired) {
    if (words.length < wordsRequired) {
        // Allocate larger of doubled size or required size
        int request = Math.max(2 * words.length, wordsRequired);
        words = Arrays.copyOf(words, request);
        sizeIsSticky = false;
    }
}

总而言之，如果您有理由相信您的值小于您的值（计数），我会说位设置只是一个好主意。例如，如果你只有两个值，但它们的值超过十亿，你将不必要地分配一个数百万元素的数组。

此外，即使在值仍然很小的情况下，此解决方案对于排序数组的性能也很差，因为 Bitset#set 将始终重新分配和复制数组，因此您的复杂性根本不是线性的，它是 [= 的二次方22=]，如果 max(nums) 非常大，这可能会很糟糕。要线性，您需要先找到最大值，在 Bitset 中分配必要的长度，然后只遍历数组。

在这一点上，使用地图更简单，适用于所有情况。如果速度真的很重要，我敢打赌 Bitset 将在特定条件下击败地图（很多值，但很小，并且 pre-sizing 所描述的位设置）。

这种情况下 bitset 的 space 复杂度是多少

What is the space complexity of bitset in this scenario

java

bitset