LeetCode 题解

积跬步，至千里。

Maximum XOR of Two Numbers in an Array

分类：LeetCode 发布于：2019-10-20 ID：421

题目描述

来源于 https://leetcode-cn.com/

给定一个非空数组，数组中元素为 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.

解法：

class Solution {
    struct Node{
        Node *next[2]{nullptr};
    };

public:
    int findMaximumXOR(vector<int>& nums) {
        Node *root = new Node;
        for(int num: nums){
            insert(num, root);
        }

        int max_xor = 0;
        for(int num: nums){
            int xor_value = find_max_xor(num, root);
            max_xor = max(max_xor, xor_value);
        }

        // destory(root);
        return max_xor;
    }

    void insert(int num, Node *root){
        int mask = 1 << 31;
        for(int i=31;i>=0;i--){
            int index = num & (1 << i) ? 1 : 0;
            if(root->next[index] == nullptr){
                root->next[index] = new Node;
            }
            root = root->next[index];
        }
    }

    int find_max_xor(int num, Node *root){
        int xor_value = 0;
        for(int i=31;i>=0;i--){
            int index = num & (1 << i) ? 1 : 0;
            if(root->next[1-index] != nullptr){
                root = root->next[1-index];
                xor_value += (1 << i);
            }else{
                root = root->next[index];
            }
        }
        return xor_value;
    }
};