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

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

给你一个整数数组 nums ,返回 nums[i] XOR nums[j] 的最大运算结果,其中 0 ≤ i ≤ j < n 。

进阶:你可以在 O(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

提示:

  • 1 <= nums.length <= 2 * 104
  • 0 <= nums[i] <= 231 - 1

题解:

前缀树

将所有数据从最高位开始取每一个bit,构建出树形结构,尽可能保证最高位为1,也就是说当循环到当前数的时候,如果当前数的bit与当前数中某一个数的某一位是相反的,那么可以保证为1,也就是最大,否则向低位继续循环。

struct Node{
    Node* next[2] = {nullptr};
};
class Solution {
public:
    void insert(int num, Node* root) {
        for (int i = 30; i >= 0; --i) {
            int t = (num >> i & 1);
            if (!root->next[t]) {
                root->next[t] = new Node();
            }
            root = root->next[t];
        }
    }
    int findMaximumXOR(vector& nums) {
        Node* root = new Node();
        for (auto val : nums) {
            insert(val, root);
        }
        int res = 0, tmp = 0;
        Node* p = root;
        for (auto val : nums) {
            p = root; tmp = 0;
            for (int i = 30; i >= 0; --i) {
                int t = (val >> i) & 1;
                if (p->next[!t]) {
                    p = p->next[!t];
                    tmp += (1 << i);
                }else p = p->next[t];
            }
            res = max(res, tmp);
        }
        return res;
    }
};

暴力+剪枝

剪枝策略两数异或最大不超过两数之和,先排序再剪枝。

class Solution {
public:
    int findMaximumXOR(vector& nums) {
        sort(nums.begin(), nums.end(), [](auto a, auto b) {return a > b;});
        int ans = 0;
        for (int i = 0; i < nums.size() - 1; i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                long long x = (long long)nums[i] + nums[j];
                if (ans > x) break;
                ans = max(ans, nums[i] ^ nums[j]);
            }
        }
        return ans;     
    }
};

   转载规则


《【Day20】421.数组中两个数的最大异或值》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
  目录