难度: 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 = [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 * 1050 <= nums[i] <= 231 - 1进阶：你可以在 O(n) 的时间解决这个问题吗？
注意：本题与主站 421 题相同： https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/
运行时间: 54 ms
内存: 30.3 MB
class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
ans = 0
maxbits = max(nums).bit_length() - 1
mask = 0
for i in range(maxbits,-1,-1):
mask |= 1 << i
want = ans | (1 << i)
seen = set()
for num in nums:
num &= mask
if want ^ num in seen:
ans = want
break
seen.add(num)
return ans
这个题解使用了一种基于贪心和位操作的方法。首先，题解试图逐步构建结果的每一位，从最高位到最低位，每一步都尽可能使结果的该位为1。具体操作是，先用一个掩码mask来确定当前正在考虑的位，然后尝试构建一个期望的最大值want。接着，使用一个集合seen存储当前所有数字经过掩码处理后的结果。对于每个数，检查want与该数的XOR结果是否已经在seen中，如果存在，则表明可以将当前want作为新的最大异或结果。这个过程从最高位开始，依次向下，每个位置都尽力使异或结果的当前位为1，从而得到全局最大的异或结果。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
ans = 0 # 初始化答案为0
maxbits = max(nums).bit_length() - 1 # 计算最大位数
mask = 0 # 初始化掩码
for i in range(maxbits,-1,-1): # 从最高位到最低位
mask |= 1 << i # 更新掩码以考虑当前位
want = ans | (1 << i) # 构建期望的最大异或结果
seen = set() # 存储已处理的数
for num in nums: # 遍历每个数
num &= mask # 应用掩码以只考虑到当前位
if want ^ num in seen: # 检查是否能通过已有数达到期望的异或结果
ans = want # 更新最大异或结果
break # 一旦找到，无需继续在当前位尝试
seen.add(num) # 将当前数添加到seen集合中
return ans # 返回最终的最大异或值
在构建最大异或结果时，从最高位到最低位逐位尝试的原因是异或运算中较高位的差异对最终结果的影响更大。例如，位于更高位置的1（如1000）比位于较低位置的1（如1）对结果的影响更大。因此，首先确保较高位的最大化可以帮助我们尽可能地获得更大的最终异或值。从最高位开始，可以在每一步中尽量保证获得当前可能的最大值，这种贪心策略保证了算法的效率和结果的优化。
在题解中，`掩码mask`的作用主要是用于限制和选择整数中的特定位，以便进行异或计算。mask的构建是通过逐位将其设为1（从最高位开始），这样通过与mask的按位与运算（num & mask），可以有效地屏蔽掉整数中位于mask中为0的位置的所有位。这样，我们只保留了从最高位到当前正在考虑的位的信息，其他更低的位则被设为0，从而帮助我们集中考虑和处理每一位的贡献，确保在构建过程中可以逐步确定每一位的最优值。
在算法中，`want`值的选择是基于当前已经获得的最大异或值`ans`来进行的。在每个循环中，通过设定`want`为`ans`再尝试将当前正在考虑的位设置为1（即ans | (1 << i)），这样的设置是希望在保持已有的高位最大异或结果的同时，进一步增加当前位的值。通过检查`want`与已有的数的异或结果是否存在于集合`seen`中，可以验证是否能够实现当前的`want`值。这种方法是贪心算法的体现，每一步都尽量保证在当前可操作的位级上达到最大值，从而整体上实现全局最大异或值。