LeetCode刷题实战421：数组中两个数的最大异或值
共 1568字，需浏览 4分钟
·
2021-10-29 19:36
Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.
示例
示例 1：
输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.
示例 2：
输入：nums = [0]
输出：0
示例 3：
输入：nums = [2,4]
输出：6
示例 4：
输入：nums = [8,10,2]
输出：10
示例 5：
输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127
解题
class Solution {
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int _val): val(_val), left(nullptr), right(nullptr) {}
};
public:
int findMaximumXOR(vector<int>& nums) {
//字典和建树都需要用到贪心算法
//建树 0->left 1->right
TreeNode root(-1);
int max = 0;
//先进行建树
for(auto num : nums){
TreeNode* ptr = &root;
for(int i = 31; i >= 0; i--){
if(num & (0x1 << i)){
if(ptr->right == nullptr){
ptr->right = new TreeNode(1);
}
ptr = ptr->right;
}else{
if(ptr->left == nullptr){
ptr->left = new TreeNode(0);
}
ptr = ptr->left;
}
}
ptr->left = new TreeNode(num);
}
//应用贪心算法，查找当前num下能产生最大异或值得组合
for(auto num : nums){
TreeNode* ptr = &root;
for(int i = 31; i >=0; i--){
if(num & (0x1 << i)){ //当前位是1，则必须查找该位为0的如果没有就走1的路
if(ptr->left){
ptr = ptr->left;
}else{
ptr = ptr->right;
}
}else{
if(ptr->right){
ptr = ptr->right;
}else{
ptr = ptr->left;
}
}
}
if((num^(ptr->left->val)) > max){
max = (num^(ptr->left->val));
}
}
return max;
}
};