e.g.
for these numbers: 1, 2, 3, 4, 0xFFFFFFFE,
we should return 1 and 0xFFFFFFFE whose XOR result is the max.
please give a algorithm with time complexity <= nlgn, O(n)would be better.
I think this can be done in O(n).
I have a two-pass algorithm:
1. The first pass builds a binary tree.
. The tree has n leaves corresponding to the n given numbers.
. Each leaf has a depth of 32.
. When you add a leaf, you start from the MSB, if 0 go left, if 1 go right.
2. In the second pass, for each number x, bit complement (m=~x) it first, and then find the best "match" of m in the tree.
The "match" looks like the following:
unsigned long BestMatch(unsigned long m, node * pRoot)
{
unsigned long match = 0;
for (int i=31; i>=0; i--)
{
match <<= 1;
BYTE bit = (m>>i)&0x01;
if (bit)
{
if (p->right)
{
p = p->right;
match ++;
}
else
{
p = p->left;
}
}
else
{
if (p->left)
{
p = p->left;
match ++;
}
else
{
p = p->right;
}
}
}
return match;
}
No comments:
Post a Comment