题目

给定一个非空数组，数组中元素为 ，其中 。

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

示例:

输入: [3, 10, 5, 25, 2, 8]
输出: 28
解释: 最大的结果是 5 ^ 25 = 28.

方案一（贪心策略）

看最高位是否异或为 1,

比如示例中：[3, 10, 5, 25, 2, 8] -> [00011,01010, 00101, 11001, 00010, 01000]

从左到右最高位参看，我们发现最高位 0, 0, 0, 1, 0, 0，说明最大数至少为 10000

还有一个公式 ，如果 a ^ b = c，那么 c ^ a = b

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:        
        res, mask = 0, 0
        for i in range(31, -1, -1):
            # 寻找数组中每个数最高位的值
            mask = mask | (1 << i)
            s = set()
            for num in nums:
                s.add(num & mask)

            # 假设最大值
            tmp = res | (1 << i)
            # a ^ b = c --> c ^ a = b
            for max_bit in s:
                if tmp ^ max_bit in s:
                    res = tmp
                    break

        return res

方案二（trie树+贪心策略）

建树时第一层节点为最高位，第二层为次高位。。。叶子节点为最低位；

搜索：

• 如果同一个节点有 0 和 1 则使用贪心策略可知应向 1 节点方向查询；
• 如果只有一个节点则向该节点查询。

class Solution:
    def __init__(self):
        self.trie = {}

    def bits(self, num):
        '''从最高位 -> 最低位返回对应bit位的值'''
        mask = 2 ** 31
        for _ in range(0, 32):
            yield 1 if num & mask != 0 else 0
            mask = mask >> 1

    def add(self, num: int):
        node = self.trie
        for bit in self.bits(num):
            if bit not in node:
                node[bit] = {}
            node = node[bit]

    def findMaximumXOR(self, nums: [int]) -> int:
        # 建树
        for num in nums:
            self.add(num)
        ret = float('-inf')
        # 对于每个数字，使用贪心策略查询树
        for num in nums:
            node = self.trie
            cur = ''
            for bit in self.bits(num):
                if not node:
                    cur += str(bit)
                if bit == 0:
                    if 1 in node:
                        node = node[1]
                        cur += '1'
                    else:
                        node = node[0]
                        cur += '0'

                if bit == 1:
                    if 0 in node:
                        node = node[0]
                        cur += '1'
                    else:
                        node = node[1]
                        cur += '0'

            num_cur = int(cur, 2)
            if num_cur > ret:
                ret = num_cur

        return ret

• 时间复杂度

原文

https://leetcode-cn.com/explore/learn/card/trie/168/practical-application-ii/651/

https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/solution/qian-zhui-shu-by-powcai/