我正在做一个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[]来跟踪我们之前是否看到了当前的数字。我的问题是这个的空间复杂度是多少?运行时似乎是O(n)，其中n是输入数组的大小。空间复杂性也是如此吗?
问题链接:https://leetcode.com/problems/find-the-duplicate-number/
您的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因子是保守的，通常它将是一个较小的因子，这就是为什么我的公式始终高估长数组的实际长度，但从不超过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;
}
}
总而言之，我想说，只有当你有理由相信你的值比你的值(count)要小的时候，比特集才是一个好主意。例如，如果您只有两个值，但它们的值超过十亿，那么您将不必要地分配一个包含数百万个元素的数组。
此外，即使在值很小的情况下，这个解决方案对于排序数组的性能也很差，因为Bitset#set总是会重新分配和复制数组，所以你的复杂性根本不是线性的，它在max(nums)中是二次的，如果max(nums)非常大，这可能是可怕的。要实现线性，首先需要找到最大值，在Bitset中分配必要的长度，然后只遍历数组。
Bitset会在特定条件下击败map(很多值，但很小，并且通过预先设置比特集的大小)。