在给定的 40 亿个整数中找到一个不存在的整数

Question

我在破解编码面试书时遇到了这个问题。

Question: Given an input file with four billion non-negative integers, provide an algorithm to generate an integer which is not contained in the file. Assume you have 1 GB of memory available for this task.

我的问题：为什么我们不能使用 BitSet 而不是 Byte[] ？这不会简化事情吗？

代码：

 long numberOflnts = ((long) Integer.MAX_VALUE) + I;
 byte[] bitfield = new byte [(int) (numberOflnts / 8)];
 void findOpenNumberQ throws FileNotFoundException {
 Scanner in = new Scanner(new FileReader("file.txt"));
 while (in.hasNextlntQ) {
 int n = in.nextlnt ();
 /* Finds the corresponding number in the bitfield by using
 * the OR operator to set the nth bit of a byte
 * (e.g., 10 would correspond to the 2nd bit of index 2 in
 * the byte array). */
 bitfield [n / 8] |= 1 « (n % 8);
 }

 for (int i = 0; i < bitfield.length; i++) {
 for (int j = 0; j < 8; j++) {
 /* Retrieves the individual bits of each byte. When 0 bit
 * is found, finds the corresponding value. */
 if ((bitfield[i] & (1 « j)) == 0) {
 System.out.println (i * 8 + j);
 return;
 }
 }
 }
}

跟进：如果您只有 10 MB 内存怎么办？假设所有值都是不同的。

Answer 1

这个问题确实允许替代解决方案。 Java 的 BitSet 可以工作，但有几个隐藏的陷阱：

Java 虚拟机需要一些内存。所以你可能运行内存不足。
BitSet 由数组支持。 Java 数组使用 32 位有符号整数作为索引，因此您实际上有 2^31 个条目。由于每个都是64位长，这就足够了。
添加位后，集合就会增长。最终，Java 代码需要为新位分配一个新数组。一不小心，这一步可能会运行 out of memory。解决方法是从头开始创建 2^32 位的数组。

在给定的 40 亿个整数中找到一个不存在的整数

Find an integer not present in given 4 billion integers

java

algorithm

large-data

bitset