0421：数组中两个数的最大异或值（★）

2016-02-25 约 738 字预计阅读 2 分钟次阅读

力扣第 421 题

题目

给你一个整数数组 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 = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127

提示：

1 <= nums.length <= 2 * 10⁵
0 <= nums[i] <= 2³¹ - 1

相似问题：

分析

#1

经典的位运算问题，可以采用试填法：

为了使结果最大，应该尽可能让二进制的高位取 1
假如前 k-1 位能取到的最大值为 M，接下来要使前 k位尽量取到 M’=(M«1)+1
假设有两个数的 k 位前缀 x、y 满足 x^y=M’，M’ 即能取到
根据异或的重要性质：如果 x^y=M’，那么 M’^x=y
因此将 k 位前缀保存在哈希表中，遍历判断即可

1
2
3
4
5
6
7
8
9


class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        L = max(nums).bit_length()
        res = 0
        for j in range(L-1,-1,-1):
            res <<= 1
            vis = {x>>j for x in nums}
            res += any(x^(res+1) in vis for x in vis)
        return res

611 ms

#2

更通用的方法是用 01 字典树
将每个数的二进制串插入字典树
然后对于每个数，查找最大的异或结果，依然是试填法
- 假如第 k 位为 bit，bit^1 在字典树中，那么该位可以取 1，并且树中往 bit^1 走
- 否则该位取 0，字典树中往 bit 走
01 字典树用数组形式可以优化时间

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


class BitTrie:
    def __init__(self,n,L):                       # 插入总长度 n-1、最长 L 的二进制串
        self.t = [[0]*n for _ in range(2)]        # 模拟树节点
        self.i = 0
        self.L = L

    def add(self, x):
        p = 0
        for j in range(self.L-1, -1, -1):
            bit = (x>>j)&1
            if not self.t[bit][p]:
                self.i += 1
                self.t[bit][p] = self.i  
            p = self.t[bit][p]
            
    def maxxor(self,x):
        p = 0
        res = 0
        for j in range(self.L-1, -1, -1):
            bit = (x>>j)&1
            if self.t[bit^1][p]:
                res |= 1 << j
                bit ^= 1
            p = self.t[bit][p]
        return res

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        L = max(nums).bit_length()
        trie = BitTrie(len(nums)*L+1,L)
        res = 0
        for x in nums:
            trie.add(x)
            res = max(res,trie.maxxor(x))
        return res

3025 ms

目录

0421：数组中两个数的最大异或值（★）

题目

分析

#1

#2

解答