Medium

题目描述

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

示例 1：

输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大的结果是 5 XOR 25 = 28.

示例 2：

输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127

提示：

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

解题思路

解题思路

这道题要求找到数组中任意两个数的最大异或值。有两种主要解法：

方法一：字典树（Trie）- 推荐解法

核心思想：构建二进制字典树，对每个数字在树中查找能产生最大异或值的路径。

异或运算的特点是：相同位为0，不同位为1。要使异或值最大，我们希望从最高位开始，尽可能让每一位都是1。

算法步骤：

  1. 构建二进制字典树，每个节点有两个子节点（0和1）
  2. 将所有数字按位插入字典树
  3. 对每个数字，在字典树中贪心地选择相反的位（0选1，1选0），这样能保证异或结果的该位为1
  4. 记录所有查询结果的最大值

方法二：逐位确定

利用异或运算的性质 a ^ b = c 等价于 a ^ c = b，逐位确定最大异或值的每一位。

时间复杂度上，字典树方法更优，且思路更直观，因此推荐使用字典树解法。

代码实现

class Solution {
public:
    struct TrieNode {
        TrieNode* children[2];
        TrieNode() {
            children[0] = children[1] = nullptr;
        }
    };
    
    TrieNode* root;
    
    void insert(int num) {
        TrieNode* node = root;
        for (int i = 30; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (!node->children[bit]) {
                node->children[bit] = new TrieNode();
            }
            node = node->children[bit];
        }
    }
    
    int findMax(int num) {
        TrieNode* node = root;
        int maxXor = 0;
        for (int i = 30; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int toggledBit = 1 - bit;
            if (node->children[toggledBit]) {
                maxXor |= (1 << i);
                node = node->children[toggledBit];
            } else {
                node = node->children[bit];
            }
        }
        return maxXor;
    }
    
    int findMaximumXOR(vector<int>& nums) {
        root = new TrieNode();
        
        for (int num : nums) {
            insert(num);
        }
        
        int maxResult = 0;
        for (int num : nums) {
            maxResult = max(maxResult, findMax(num));
        }
        
        return maxResult;
    }
};

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        class TrieNode:
            def __init__(self):
                self.children = {}
        
        root = TrieNode()
        
        # Insert all numbers into trie
        for num in nums:
            node = root
            for i in range(30, -1, -1):
                bit = (num >> i) & 1
                if bit not in node.children:
                    node.children[bit] = TrieNode()
                node = node.children[bit]
        
        max_xor = 0
        
        # Find maximum XOR for each number
        for num in nums:
            node = root
            current_xor = 0
            for i in range(30, -1, -1):
                bit = (num >> i) & 1
                toggled_bit = 1 - bit
                
                if toggled_bit in node.children:
                    current_xor |= (1 << i)
                    node = node.children[toggled_bit]
                else:
                    node = node.children[bit]
            
            max_xor = max(max_xor, current_xor)
        
        return max_xor

public class Solution {
    public class TrieNode {
        public TrieNode[] Children = new TrieNode[2];
    }
    
    private TrieNode root;
    
    private void Insert(int num) {
        TrieNode node = root;
        for (int i = 30; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (node.Children[bit] == null) {
                node.Children[bit] = new TrieNode();
            }
            node = node.Children[bit];
        }
    }
    
    private int FindMax(int num) {
        TrieNode node = root;
        int maxXor = 0;
        for (int i = 30; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int toggledBit = 1 - bit;
            if (node.Children[toggledBit] != null) {
                maxXor |= (1 << i);
                node = node.Children[toggledBit];
            } else {
                node = node.Children[bit];
            }
        }
        return maxXor;
    }
    
    public int FindMaximumXOR(int[] nums) {
        root = new TrieNode();
        
        foreach (int num in nums) {
            Insert(num);
        }
        
        int maxResult = 0;
        foreach (int num in nums) {
            maxResult = Math.Max(maxResult, FindMax(num));
        }
        
        return maxResult;
    }
}

var findMaximumXOR = function(nums) {
    class TrieNode {
        constructor() {
            this.children = {};
        }
    }
    
    const root = new TrieNode();
    
    // Insert all numbers into trie
    for (let num of nums) {
        let node = root;
        for (let i = 30; i >= 0; i--) {
            const bit = (num >> i) & 1;
            if (!(bit in node.children)) {
                node.children[bit] = new TrieNode();
            }
            node = node.children[bit];
        }
    }
    
    let maxXor = 0;
    
    // Find maximum XOR for each number
    for (let num of nums) {
        let node = root;
        let currentXor = 0;
        for (let i = 30; i >= 0; i--) {
            const bit = (num >> i) & 1;
            const toggledBit = 1 - bit;
            
            if (toggledBit in node.children) {
                currentXor |= (1 << i);
                node = node.children[toggledBit];
            } else {
                node = node.children[bit];
            }
        }
        
        maxXor = Math.max(maxXor, currentXor);
    }
    
    return maxXor;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
字典树O(n × 31)O(n × 31)
逐位确定O(n × 31²)O(n)

其中 n 是数组长度，31 是整数的最大位数。字典树方法在时间和空间上都更优。

相关题目