LeetCode刷题日记2021-5-16/421. 数组中两个数的最大异或值/二叉树

仅供自己学习记录

LeetCode刷题日记2021-5-16

题目描述

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

**进阶：**你可以在 O(n) 的时间解决这个问题吗？

示例 1：

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

示例 2：

输入：nums = [0]
输出：0

示例 3：

输入：nums = [2,4]
输出：6

示例 4：

输入：nums = [8,10,2]
输出：10

示例 5：

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

提示：

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

题解思路

使用双重循环的话 时间复杂度为n^2 会超时 所以我们采用前缀二叉树来完成

• 从高位到低位构建一棵只有0和1的二叉树
• 然后在二叉树中搜索

题解代码

class Tree():
	def __init__(self):
		self.left=None
		self.right=None
class Solution:
	def findMaximumXOR(self, nums: List[int]) -> int:
		root=Tree()
		high_bit=30
		
		def add(num):
			cur=root
			for k in range(high_bit,-1,-1):
				bit=(num>>k)&1
				if bit==1:
					if not cur.right:
						cur.right=Tree()
					cur=cur.right
				else:
					if not cur.left():
						cur.left=Tree()
					cur=cur.left
		def check(num):
			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*x+1
					else:
						cur=cur.left
						x=x*2
				else:
					if cur.left:
						cur=cur.left
						x=x*2+1
					else:
						x=x*2
			return x
		
		n=len(nums)
		x=0
		for i in range(1,n):
			add(nums[i-1]
			x=max(x,check(x,nums[i])
		
		return x