我最近浏览了一本编码书，遇到了这个有趣的问题。
数组A包含从0到n的所有整数，除了一个数字是
失踪。在此问题中，我们无法通过单个操作访问A中的整个整数。
A的元素用二进制表示，并且我们可以使用的唯一操作
要访问它们，是“获取A [i]的第j位”，这需要花费固定的时间。写代码到
找到丢失的整数。您可以在0（n）时间内完成吗？
这本书要做的是经过三页的过程，解释了如何有效地解决此问题。老实说，对我来说有点像TL; DR，所以我制定了自己的解决方案，并将其与本书进行了比较。我只是想知道我的解决方案是否真正有效（因为似乎怀疑当几分钟之内就可以起草一个更简单的解决方案时，本书的答案可能是如此冗长和详尽）。
这是本书的解决方案：
1 public int findMissing(ArrayList<BitInteger> array) {
2 /* Start from the least significant bit, and work our way up */
3 return findMissing(array, 0);
4 }
5
6 public int findMissing(ArrayList<BitInteger> input, int column) {
7 if (column >= BitInteger.INTEGER_SIZE) { // We're done!
8 return 0;
9 }
10 ArrayList<BitInteger> oneBits =
11 new ArrayList<BitInteger>(input.size()/2);
12 ArrayList<BitInteger> zeroBits =
13 new ArrayList<BitInteger>(input.size()/2);
14
15 for (BitInteger t : input) {
16 if (t.fetch(column) == 0) {
17 zeroBits.add(t);
18 } else {
19 oneBits.add(t);
20 }
21 }
22 if (zeroBits. size() <= oneBits.size()) {
23 int v = findMissing(zeroBits, column + 1);
24 return (v « 1) | 0;
25 } else {
26 int v = findMissing(oneBits, column + 1);
27 return (v « 1) | 1;
28 }
29 }
我自己的解决方案（对我来说似乎是相同的O（n）时间复杂度，但在位置上用O（1）空间复杂度完成）要简单得多。我将“获取”方法定义为采用两个参数。第一个指定第x位，第二个指定索引号。我假设已经给出了此方法，因为在这样的问题中已经提到了该方法（“获取A [i]的第j位”）。基本上，我只是检查最低位是否在1和0之间交替-就是全部。
int findMissing(int[] arr) {
int lowBit = fetch(0, 0); // fetch the 0th bit of arr[0]
if(lowBit != 0) {
return 0; // obviously, the array is not starting at 0, so 0 must be what is removed
}
int expectedNextBit = 1; // we expect the lowest bit to be 1
for(int x = 1; x < arr.length; x++) {
lowBit = fetch(0, x); // fetch the 0th bit (lowest) of arr[x]
if(lowBit != expectedNextBit) {
return x;
}
expectedNextBit = lowBit ^ 0x1;
}
return arr.length;
}
我的问题是-我自己的解决方案出了什么问题？我是CS大二的本科生，而这本书是由博士所写的，所以我非常怀疑我的答案实际上会比他们的答案更好。
最佳答案
您的解决方案错误地假定输入数字已排序。如果输入的是[0, 2, 1, 3, 5]，则解决方案将错误地报告1，即使它出现在阵列的后面。
关于java - 在整数数组中查找缺失的整数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33967374/