[Leetcode 421] Maximum XOR of Two Numbers in an Array

作者 Shilei Tian 日期 2017-01-03
[Leetcode 421] Maximum XOR of Two Numbers in an Array

题目要求

Given a non-empty array of numbers, $a_{0},a_{1},a_{2},\dots,a_{n-1}$, where $0 \leq a_i<2^{31}$.

Find the maximum result of $a_i\oplus a_j$, where $0\leq i,j< n$.

Could you do this in $O(n)$ runtime?

Example:

Input: [3, 10, 5, 25, 2, 8]

Output: 28

Explanation: The maximum result is $5\oplus25=28$.

解题思路

题目要求很简单,就是从一个序列中找到一对儿值 $a_i,a_j$,使得 $a_i\oplus a_j$ 的值最大,但是对于复杂度的要求比较高,是 $O(n)$,这样就不能简单的让每一对元素进行异或操作记录最大值了。那么应该怎么做呢?

这里介绍一个我之前没听说的数据结构——Trie,又称前缀树或字典树或基数树。它的定义咱们在这里不赘述,直接讲一下它是怎么与这道题应用的。本题中,每一个元素是一个 32unsigned int,那么我们可以用一个 Trie 树来存储它,从该元素的最左边那一位开始起,如果该位是 0,那么就建立根节点的左孩子,如果该位是 1,那么就建立根节点的右孩子;这样一步步递归建立,我们就可以唯一的建立起一条从根节点到叶子节点的路径,顺着该路径,我们就可以得到这个元素。那么整个序列的元素我们就可以用一棵深度为 32 的 Trie 树来存储,每个元素都对应该树上的一个叶子节点。

那 Trie 在本题上有什么用呢?考虑这样一个问题,如果两个数进行异或,想让它的结果比较大,这两个数应该满足怎么样的性质?是不是应该让他们的高位尽可能的不一样?考虑两个数 $a=a_{31}a_{30}\dots a_{0}$ 和 $b=b_{31}b_{30}\dots b_{0}$,如果 $a_{31}$ 和 $b_{31}$ 不一样,那 $a\oplus b=2^{31}+x$,这里 $x=a’\oplus b’$,$a’=a_{30}\dots a_{0}$ 和 $b’=b_{30}\dots b_{0}$,以此类推。那我们现在给定 $a$,想要找到那个能使 $a \oplus b$ 尽可能大的 $b$,有了 Trie,我们只需要从高到底的判断 $a$ 的每一位 $a_i$,如果它是 1,那么我们就向该位是 0 的那个方向找,如果这个方向对应的子树是空,这就说明,我们该序列中所有的元素这一位都是 1,那么这一位无论与谁异或,得到的都是 0;如果这个方向对应的子树不为空,就说明我们至少存在一个数,使得它能为两个数异或的结果贡献 $2^{i}$。同理,如果该位是 0,那么我们就向该位是 1 的那个方向找。这个策略有点像贪心,但是为什么贪心可以获得最优解呢?这个道理很显然,比如 8 对应 1000,那么它显然大于 0111。这样,我们对序列中的每一个元素都让它进行一次上述过程,存储那个最大的值就可以了。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
class TrieNode {
public:
TrieNode() {
next[0] = next[1] = NULL;
}

TrieNode* next[2];
};

int findMaximumXOR(vector<int>& nums) {
TrieNode* root = buildTrie(nums);
int ret = INT_MIN;
for (auto num : nums) {
ret = max(ret, findMaximumXOR(root, num));
}
return ret;
}

private:
TrieNode* buildTrie(vector<int>& nums) {
TrieNode* root = new TrieNode();
for (auto num : nums) {
TrieNode* p = root;
for (int i = 31; i >= 0; --i) {
int bit = (num >> i) & 0x1;
if (p->next[bit] == nullptr) {
p->next[bit] = new TrieNode();
}
p = p->next[bit];
}
}
return root;
}

int findMaximumXOR(TrieNode* root, const int num) {
int ret = 0;
TrieNode* p = root;
for (int i = 31; i >= 0; --i) {
int bit = (num >> i) & 0x1 ? 0 : 1;
ret <<= 1;
if (p->next[bit]) {
ret |= 0x1;
p = p->next[bit];
} else {
ret |= 0;
p = p->next[bit ? 0 : 1];
}
}
return ret;
}
};

该算法中的循环应该一共进行了 $2 \times 32 \times n$ 次,其中 $32 \times n$ 次用来构建 Trie,剩下 $32 \times n$ 次来进行查找当前元素与其他元素异或能产生最大的结果。

总结

有了 Trie 的概念,我们可以通过前缀就过滤掉那些不符合要求的集合,使得搜索起来速度非常快。这个数据结构需要多加练习。