Leetcode 剑指 Offer II 067.数组中两个数的最大异或值

题目难度: 中等

原题链接

今天继续更新 Leetcode 的剑指 Offer（专项突击版）系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

给定一个整数数组 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 * 10^5
• 0 <= nums[i] <= 2^31 - 1
• 进阶：你可以在 O(n) 的时间解决这个问题吗？

题目思考

1. 如何优化时间复杂度?

解决方案

思路

• 分析题目, 一个最直接的思路就是两重循环求每个数字对的异或值, 从而得到最大值
• 不过这样做的时间复杂度达到了 O(N^2), 按照题目规模肯定会超时, 如何优化呢?
• 假设数组的最大异或值 x=ai^aj, 那么一定有 pk(x)=pk(ai)^pk(aj) (pk(n)表示 n 的前 k 位)
• 根据异或结合律, 则有 pk(ai)=pk(x)^pk(aj), 我们可以利用集合判断当前 pk(x)的最低位应该是 1 还是 0, 具体步骤如下:
  1. 令 res 记录最大异或值的当前前缀部分 pk(x), 初始化为 0
  2. 然后按照前缀长度从小到大的顺序遍历
  3. 对于前缀长度 k, 遍历所有数字, 右移 k 位求出对应的前缀, 并加入集合中
  4. 接下来假设最大异或值的这一位是 1, 也即 res 左移一位并加 1
  5. 再遍历所有数字, 将 res 与对应数字的前缀异或
  6. 如果某个异或的结果在当前前缀集合里, 则说明该位真的可以为 1, 即满足pk(ai)=pk(x)^pk(aj), 跳出循环
  7. 如果遍历结束仍未找到, 则说明不存在某个异或结果在前缀集合中, 该位只能为 0, 将 res 减去 1
  8. 最后, 遍历完所有前缀长度后的 res 即为所求
• 下面代码中有详细的注释, 方便大家理解

复杂度

• 时间复杂度 O(N): 外层循环次数是常数, 内层循环每次只需要遍历整个数组一遍
• 空间复杂度 O(N): 需要额外的集合存储每次遍历的所有数字前缀

代码

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        res = 0
        for k in range(32)[::-1]:
            v = set()
            for x in nums:
                # 将所有数字的pk前缀加入集合
                v.add(x >> k)
            # 先假设当前位可以为1
            res = (res << 1) + 1
            for x in nums:
                if res ^ (x >> k) in v:
                    # res与该前缀的异或结果已经在集合中了, 说明最终最大异或值的这一位是1
                    break
            else:
                # 异或结果不在前缀集合中, 这一位只能为0
                res -= 1
        return res

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊