Java实现 LeetCode 421 数组中两个数的最大异或值

421. 数组中两个数的最大异或值

给定一个非空数组,数组中元素为 a0, a1, a2, … , an-1,其中 0 ≤ ai < 231 。

找到 ai 和aj 最大的异或 (XOR) 运算结果,其中0 ≤ i, j < n 。

你能在O(n)的时间解决这个问题吗?

示例:

输入: [3, 10, 5, 25, 2, 8]

输出: 28

解释: 最大的结果是 5 ^ 25 = 28.

PS:

前缀树

class Solution {

    class TrieNode {

        TrieNode zero;

        TrieNode one;

        int val;

        TrieNode() {

        }
} class Trie { TrieNode root; Trie() {
root = new TrieNode();
} void insert(int num) {
TrieNode node = root;
for (int i = 31; i >= 0; i--) {
int bit = num & (1 << i);
if (bit == 0) {
if (node.zero == null) {
node.zero = new TrieNode();
}
node = node.zero;
} else {
if (node.one == null) {
node.one = new TrieNode();
}
node = node.one;
}
}
node.val = num;
} int find(int num) {
TrieNode node = root;
for (int i = 31; i >= 0; i--) {
int bit = num & (1 << i);
if (bit == 0) {
node = node.one == null ? node.zero : node.one;
} else {
node = node.zero == null ? node.one : node.zero;
}
}
return node.val;
}
} // 数组中两个数的最大异或值
public int findMaximumXOR(int[] nums) {
Trie trie = new Trie();
for (int num : nums) {
trie.insert(num);
}
int res = 0;
for (int num : nums) {
int other = trie.find(num);
res = Math.max(res, num ^ other);
}
return res;
}
}
上一篇:MySQL online ddl原理


下一篇:LeetCode 421. 数组中两个数的最大异或值(Maximum XOR of Two Numbers in an Array) 71