CareerCup-5.7
An array A[1 n] contains all the integers from 0 to n except for one number which is missing In this problem, we cannot access an entire integer in A with a single operation The elements of A are represented in binary, and the only operation we can use to access them is “fetch the jth bit of A[i]”, which takes constant time. Write code to find the missing integer. Can you do it in O(n) time? 没有使用答案的递归的方法，尝试用异或在O(n)时间内解决
#include <iostream>
using namespace std;
#define N 6
class Array
{
public:
Array()
{
for(int i=0; i<=N; i++)
{
data[i] = i;
}
data[0] ^= data[3];
data[3] ^= data[0];
data[0] ^= data[3];
};
bool fetchBit(int i, int j)
{
if(i < 1 || i > N || j < 0 || j > 30)
return -1;
return getBit(data[i], j);
};
void findMissing()
{
int t = 0;
for(int i=1; i<=N; i++)
t ^= i;
int r = 0;
int s;
for(int j=30; j>=0; j--)
{
s=0;
for(int i=1; i<=N; i++)
{
s ^= fetchBit(i, j);
}
r = (r << 1) + s;
}
cout<<(t ^ r)<<endl;
};
private:
int getBit(int d, int j)
{
return ((d & (1 << j)) >> j);
};
int data[N+1];
};
int main()
{
Array array;
array.findMissing();
system("pause");
};
随后发现答案的代码有问题，第48和50行应该移位的是1和0，移位值是column。同时还需要将数据总数填充为2^n-1。于是修正了代码，并把自己的代码用Java实现了一下。
import java.util.ArrayList;
class BitInteger {
BitInteger(int i) {
data = i;
}
public static int INTEGER_SIZE = 31;
Integer data;
int fetch(int i) {
return (data & (1 << i)) >> i;
}
}
public class Test {
static int findMissing(ArrayList<BitInteger> array) {
int size = array.size();
int t = 1;
while (t < size)
t = t << 1;
if ((size & (size - 1)) > 0) {
array = (ArrayList<BitInteger>) array.clone();
int n = (int) Math.pow(2, t) - 1;
while (array.size() < n) {
array.add(new BitInteger(array.size() + 1));
}
}
return findMissing(array, t - 1);
}
static int findMissing(ArrayList<BitInteger> input, int column) {
if (column < 0) { // Base case and error condition
return 0;
}
ArrayList<BitInteger> oddIndices = new ArrayList<BitInteger>();
ArrayList<BitInteger> evenIndices = new ArrayList<BitInteger>();
for (BitInteger t : input) {
if (t.fetch(column) == 0) {
evenIndices.add(t);
} else {
oddIndices.add(t);
}
}
// System.out.println(oddIndices.size() + " " + evenIndices.size());
if (oddIndices.size() >= evenIndices.size()) {
return (findMissing(evenIndices, column - 1)) | 0 << column;
} else {
return (findMissing(oddIndices, column - 1)) | 1 << column;
}
}
static int findMissingTwo(ArrayList<BitInteger> array) {
int t = 0;
for (int i = 1; i <= array.size(); i++) {
t ^= i;
}
int r = 0;
for (int j = BitInteger.INTEGER_SIZE; j >= 0; j--) {
int s = 0;
for (int i = 0; i < array.size(); i++) {
s ^= array.get(i).fetch(j);
}
r = (r << 1) + s;
}
return t ^ r;
}
public static void main(String[] argv) {
ArrayList<BitInteger> list = new ArrayList<BitInteger>();
for (int i = 0; i < 13; i++) {
if (i != 3)
list.add(new BitInteger(i));
}
System.out.println(findMissing(list));
System.out.println(findMissingTwo(list));
}
}
