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

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

原始题目链接：https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/

给你一个整数数组 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 * 105
0 <= nums[i] <= 231 - 1

解题思路：

这道题是位操作，并且应用一个法则：如果 a ^ b = max 成立 ，max 表示当前得到的“最大值”， 那么一定有 max ^ b = a 成立。具体实现看代码。

代码实现：

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        ans = 0
        # 掩码，位操作，用于获得前缀，初始化为0
        mask = 0

        # 因为 0 <= nums[i] <= 2的31次方 - 1
        # 循环31次即可，为了获取最大值，所以从最高位开始操作
        for i in range(30, -1, -1):
            # 从高位开始获得掩码
            mask |= (1 << i)

            # 将前缀都放进一个哈希表中
            s = set()
            # 前缀的获取是通过掩码和数字本身进行按位与操作
            # 前缀存到set中用于后面的异或结果查找
            for num in nums:
                s.add(mask & num)

            # 假设最大的异或值的从高位开始是1
            # 所以用ans按位或操作，获得一个临时异或最大值temp
            # 去set中查找是否在num中存在一个数，和temp进行异或操作
            # 使得当前的位是1
            temp = ans | (1 << i)

            # 然后根据法则：如果 a ^ b = max 成立 ，max 表示当前得到的“最大值”，
            # 那么一定有 max ^ b = a 成立
            # 此时temp看成是max，prefix看成是b，s中的值看成是a
            for prefix in s:
                if temp ^ prefix in s:
                    # 更新异或最大值
                    ans = temp
                    break
            # 清空本次的前缀
            s.clear()

        return ans

参考文献：
https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/solution/li-yong-yi-huo-yun-suan-de-xing-zhi-tan-xin-suan-f/