题目描述
给定一个整数数组 nums ,返回 nums[i] XOR nums[j] 的最大运算结果,其中 0 ≤ i ≤ j < n 。
提示:
1 <= nums.length <= 2 * 104
0 <= nums[i] <= 231 - 1
进阶:你可以在 O(n) 的时间解决这个问题吗?
样例
输入:nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出:127
Trie
字典树:利用节点实现
技巧: x == 0 ?1 :0; ----->>>>> x ^= 1;
也可以用数组实现,但是数组太大,虽然更快
时间复杂度
O(n)
C++ 代码
class Solution {
public:
class TreeNode {
public:
TreeNode* next[2];
TreeNode () {
for(auto& n : next) n = NULL;
};
};
TreeNode* buildTree(vector<int>& nums) {
TreeNode* root = new TreeNode(), *p;
for (int num : nums) {
p = root;
for (int i = 31; i >= 0; i--) {
int index = (num >> i) & 1;
if (p->next[index] == NULL)
p->next[index] = new TreeNode();
p = p->next[index];
}
}
return root;
}
int helper(TreeNode* cur, int num) {
int res = 0;
for (int i = 31; i >= 0; i--) {
int index = (num >> i) & 1;
if (cur->next[index^1]) {
res |= 1 << i;
cur = cur->next[index^1];
} else cur = cur->next[index];
}
return res;
}
int findMaximumXOR(vector<int>& nums) {
int res = 0;
TreeNode* root = buildTree(nums);
for (auto x : nums)
res = max(res, helper(root, x));
return res;
}
};