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

￡神魔★判官ぃ 2023-01-21 12:28 155阅读 0赞

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

## Idea ##

假设选择了数组中的元素ai和aj使得它们达到最大按位异或结果x: x = a i ⊕ a j x=a\_\{i\}⊕a\_\{j\} x=ai⊕aj，其中⊕表示按位异或运算。

根据异或运算的性质， x = a i ⊕ a j x=a\_\{i\}⊕a\_\{j\} x=ai⊕aj等价于 a j = a i ⊕ x a\_\{j\}=a\_\{i\}⊕x aj=ai⊕x，根据这一变换，可以设计一种\[从高位到低位依次确定x二进制表示的每一位\]的方法，以此得到x的值。

数组中的元素都在\[0, 231)的范围内，可以将每一个数都表示为一个长度为31位的二进制数（不满31位补前导0）字符串，然后可以从最高位第30个二进制位开始依次确定x的每一位是0还是1。

由于需要找出最大的x，因此在枚举每一位时，需要先判断x的这一位是否能取到1，如果能，就取这一位为1，否则取这一位为0。

将字符串放入字典树中，那么在字符串中查询一个字符串的过程，就是从高位开始确定每一个二进制位的过程。

x = a i ⊕ a j x=a\_\{i\}⊕a\_\{j\} x=ai⊕aj，枚举ai，将a0, a1, …, ai-1作为aj放入字典树，希望找到使得x达到最大值的aj。

从字典树的根节点开始进行遍历，遍历的\[参照对象\]为ai，根据ai的第x个二进制位时0还是1确定应该走哪个子节点。

假设当前遍历到第k个二进制位：

*  如果ai的第k个二进制位为0，那么应该往表示1的子节点走。如果不存在表示1的子节点，就只能往表示0的子节点走。
 *  如果ai的第k个二进制位为1，那么应该往表示0的子节点走。如果不存在表示0的子节点，就只能往表示1的子节点走。

遍历完所有的31个二进制位后，得到ai可以通过异或运算得到的最大x。

## Code ##

### Python ###

from typing import List
    
    
    class Trie:
    	def __init__(self):
    		self.left, self.right = None, None
    
    
    class Solution:
    	def findMaximumXOR(self, nums: List[int]) -> int:
    		root = Trie()
    		HIGH_BIT = 30
    
    		def add(num: int) -> None:
    			cur = root
    			for k in range(HIGH_BIT, -1, -1):
    				bit = (num >> k) & 1
    				if bit == 0:
    					if not cur.left:
    						cur.left = Trie()
    					cur = cur.left
    				else:
    					if not cur.right:
    						cur.right = Trie()
    					cur = cur.right
    
    		def check(num: int) -> int:
    			cur = root
    			x = 0
    			for k in range(HIGH_BIT, -1, -1):
    				bit = (num >> k) & 1
    				if bit == 0:
    					if cur.right:
    						cur = cur.right
    						x = x * 2 + 1
    					else:
    						cur = cur.left
    						x = x * 2
    				else:
    					if cur.left:
    						cur = cur.left
    						x = x * 2 + 1
    					else:
    						cur = cur.right
    						x = x * 2
    			return x
    		
    		n, x = len(nums), 0
    		for i in range(1, n):
    			add(nums[i - 1])
    			x = max(x, check(nums[i]))
    		return x

[421.]: https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/