LeetCode 数组中两个元素的最大异或题解
题目描述
给定一个整数数组 nums，返回 nums[i] XOR nums[j] 的最大结果。
示例：
输入：nums = [3,10,5,25,2,8]
输出：28
解题思路
方法：字典树
思路：
- 使用字典树存储所有数字的二进制表示。
- 遍历数组，对于每个数字，在字典树中查找与其异或结果最大的数字。
- 从最高位开始，尽量选择与当前位不同的路径。
复杂度分析：
- 时间复杂度：O(n * L)，L 是二进制位数。
- 空间复杂度：O(n * L)。
代码实现
class TrieNode: def __init__(self): self.children = {} class Trie: def __init__(self): self.root = TrieNode() def insert(self, num): node = self.root for i in range(31, -1, -1): bit = (num >> i) & 1 if bit not in node.children: node.children[bit] = TrieNode() node = node.children[bit] def find_max_xor(self, num): node = self.root xor_val = 0 for i in range(31, -1, -1): bit = (num >> i) & 1 opposite = 1 - bit if opposite in node.children: xor_val = xor_val * 2 + 1 node = node.children[opposite] else: xor_val = xor_val * 2 node = node.children[bit] return xor_val def find_maximum_xor(nums): trie = Trie() for num in nums: trie.insert(num) max_xor = 0 for num in nums: max_xor = max(max_xor, trie.find_max_xor(num)) return max_xor # 测试 def test_find_maximum_xor(): nums = [3, 10, 5, 25, 2, 8] print(find_maximum_xor(nums)) # 输出：28 if __name__ == "__main__": test_find_maximum_xor()总结
字典树可以用于求最大异或值，从最高位开始，尽量选择与当前位不同的路径。
