421 Maximum XOR of Two Numbers in an Array 数组中两个数的最大异或值

Description:
Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 ≤ i ≤ j < n.

Follow up:
Could you do this in O(n) runtime?

Example:

Example 1:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

Example 2:

Input: nums = [0]
Output: 0

Example 3:

Input: nums = [2,4]
Output: 6

Example 4:

Input: nums = [8,10,2]
Output: 10

Example 5:

Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127

Constraints:

1 <= nums.length <= 2 * 10^4
0 <= nums[i] <= 2^31 - 1

题目描述:
给定一个非空数组，数组中元素为 a0, a1, a2, … , an-1，其中 0 ≤ ai < 2^31 。

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

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

示例 :

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

输出: 28

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

思路:

前缀树/哈希表
异或的一个性质: a ^ b = c -> a ^ c = b & b ^ c = a
那么就转化为二进制找高位 1, 越多越好
将异或值存储在表中, 用掩码查找该位是否能为 1即可
时间复杂度O(n), 空间复杂度O(n)

代码:
C++:

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

Java:

class Solution {
    public int findMaximumXOR(int[] nums) {
        int result = 0, cur = 0, mask = 0;
        for (int i = 30; i >= 0; i--) {
            mask = mask | (1 << i);
            Set<Integer> set = new HashSet<>();
            for (int num : nums) set.add(num & mask);
            cur = result | (1 << i);
            for (Integer j : set) {
                if (set.contains(j ^ cur)) {
                    result = cur;
                    break;
                }
            }
        }
        return result;
    }
}

Python:

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        l, result = len(bin(max(nums))[2:]), 0
        for i in range(l)[::-1]:
            result <<= 1
            cur = result | 1
            d = {num >> i for num in nums}
            result |= any(cur ^ j in d for j in d)     
        return result