题目

难度：★★★☆☆
类型：数组
方法：数学

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给定一个非空数组，数组中元素为 a0, a1, a2, … , an-1，其中 0 ≤ ai < 231 。

找到 ai 和aj 最大的异或 (XOR) 运算结果，其中0 ≤ i, j < n 。

你能在O(n)的时间解决这个问题吗？

示例:

输入: [3, 10, 5, 25, 2, 8]

输出: 28

解释: 最大的结果是 5 ^ 25 = 28.

解答

暴力求解方式这里不再给出，我们直接上手O(n)算法。这道题目需要使用到异或的重要性质：

如果a ^ b = c 那么a ^ c = b, b ^ c = a，也就是说，如果三个变量可以通过异或组成等式，那么三个变量无论如何交换位置，等式都是成立的。

除此之外，异或还有其他运算法则请大家留意：

交换律：a ^ b = b ^ a
结合律：a ^ (b ^ c) = (a ^ b) ^ c
a ^ a = 0
a ^ 0 = a

交换律和结合律常常被用来解决找出数组中唯一没有出现过两次的数之类的题目。

关于本题的详细证明参照大佬解析

对于给定的数组，其中可能存在本多整数，我们把这些整数都看作二进制，并以最长的串为标准，将这些二进制串前方补齐零。

为了获得最大的异或值，我们的希望是较高位尽可能都是1，需要从最高位开始研究，对于[3, 10, 5, 25, 2, 8]来说，它们转换为二进制后最长的串是25对应的，也就是5位二进制数，那么将其他数字不足5位二进制数的前方都补零，从最高位5到最低位1逐位研究，设i为当前研究的位，那么i在程序中的范围为逆序的4到0。准备一个二进制的掩码，用于提取二进制串的前缀，例如i=2时，当前掩码为11100，用这个掩码与原始数组中每个元素做与运算，就可以达到提取前缀的作用，提取的前缀放在一个集合中。

对于当前研究位i，我们暂且认为存在两个数字，可以使得这两个数字的异或为1，把期望的结果设为res_candidate，我们可以遍历前缀集合中的每个元素，如果发现有元素与期望结果的异或可以在集合中找到，说明当前位的最终异或结果是可以是1的，如果不满足条件，则继续使用原来的结果。

class Solution:
    def findMaximumXOR(self, nums) -> int:
        res = mask = 0                                      # 初始化结果变量和前缀掩码

        for i in reversed(range(len(bin(max(nums)))-2)):    # 从最大的数字的二进制最高位向右开始遍历
            current_bit = 1 << i                            # 当前研究的是哪一位
            mask = mask | current_bit                       # 将当前位置及其之前的所有位置作为掩码，例如111000
            prefix_set = set(num & mask for num in nums)    # 根据掩码提出来所有数字的前缀

            res_candidate = res | current_bit               # 姑且临时地认为，当前研究的这个数字位，是可以通过数组中的两个数在该位异或得到的
            for prefix in prefix_set:                       # 遍历前缀集合中的所有元素
                if res_candidate ^ prefix in prefix_set:    # 研究当前前缀prefix与候选结果res_candidate的异或是否能在前缀集合中找到prefix2，如果有prefix ^ res_candidate == prefix2, 那么一定有prefix ^ prefix2 == res_candidate
                    res = res_candidate                     # 满足条件，转正
                    break                                   # 既然找到了，就不用继续寻找了，继续向右遍历下一位就好
        return res                                          # 返回最终结果

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析