每个查询的最大异或值

难度: Medium

给你一个有序数组 nums ，它由 n 个非负整数组成，同时给你一个整数 maximumBit 。你需要执行以下查询 n 次：

找到一个非负整数 k < 2^maximumBit ，使得 nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k 的结果 最大化 。k 是第 i 个查询的答案。
从当前数组 nums 删除最后一个元素。

请你返回一个数组 answer ，其中 answer[i]是第 i 个查询的结果。

示例 1：

输入：nums = [0,1,1,3], maximumBit = 2
输出：[0,3,2,3]
解释：查询的答案如下：
第一个查询：nums = [0,1,1,3]，k = 0，因为 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3 。
第二个查询：nums = [0,1,1]，k = 3，因为 0 XOR 1 XOR 1 XOR 3 = 3 。
第三个查询：nums = [0,1]，k = 2，因为 0 XOR 1 XOR 2 = 3 。
第四个查询：nums = [0]，k = 3，因为 0 XOR 3 = 3 。

示例 2：

输入：nums = [2,3,4,7], maximumBit = 3
输出：[5,2,6,5]
解释：查询的答案如下：
第一个查询：nums = [2,3,4,7]，k = 5，因为 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7。
第二个查询：nums = [2,3,4]，k = 2，因为 2 XOR 3 XOR 4 XOR 2 = 7 。
第三个查询：nums = [2,3]，k = 6，因为 2 XOR 3 XOR 6 = 7 。
第四个查询：nums = [2]，k = 5，因为 2 XOR 5 = 7 。

示例 3：

输入：nums = [0,1,2,2,5,7], maximumBit = 3
输出：[4,3,6,4,6,7]

提示：

nums.length == n
1 <= n <= 10⁵
1 <= maximumBit <= 20
0 <= nums[i] < 2^maximumBit
nums 中的数字已经按升序排好序。

Submission

运行时间: 61 ms

内存: 31.2 MB

class Solution:
    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:
        #考虑异或前缀和即可,没必要真的模拟删除
        ans=[]
        x_or,max_num=0,(1<<maximumBit)-1
        for num in nums:
            x_or^=num
            ans.append(x_or^max_num)
        return ans[::-1]

Explain

这个题解使用了前缀异或和的思路，从而避免了对数组进行实际的元素删除操作。首先，通过遍历整个数组，计算从第一个元素到当前元素的所有异或和，并存储到变量 x_or 中。利用异或操作的性质，x_or 可以在常数时间内通过上一个 x_or 值和当前元素进行更新。然后为了找到每一步的最大值，我们需要找到一个 k 值，使得 x_or XOR k 的结果最大。为了达到这一点，我们可以将 x_or 与 (1 << maximumBit) - 1 进行异或操作，该值实际上是在 maximumBit 位都为1的最大数字，这样可以确保异或结果的最大化。结果数组在完成遍历后需要反转，以匹配题目中逐步删除元素的顺序。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:
        ans = []  # 用于存储每个查询的最大异或结果
        x_or = 0  # 用于计算当前的异或前缀和
        max_num = (1 << maximumBit) - 1  # 计算最大的 k 值，即 maximumBit 位全为1的数
        for num in nums:  # 遍历数组，计算前缀异或和
            x_or ^= num  # 更新前缀异或和
            ans.append(x_or ^ max_num)  # 计算当前前缀异或和与最大数的异或结果，并添加到答案列表中
        return ans[::-1]  # 反转结果列表，以匹配删除数组元素的顺序

Explore

异或操作的一个关键性质是，两个不同位的异或结果为1。因此，为了使 `x_or ^ k` 的结果尽可能大，我们希望 `k` 中的每一位都能最大化 `x_or` 对应位的异或结果。如果 `x_or` 的某一位是0，那么 `k` 的对应位为1时，异或结果才为1，反之亦然。因此，`k` 的选择应使其与 `x_or` 的每一位尽可能不同。`max_num`，即 `(1 << maximumBit) - 1`，是一个所有有效位皆为1的数字，这确保了在有效位内 `k` 可以选择任何值来最大化与 `x_or` 的异或结果。

`max_num` 的计算方法 `(1 << maximumBit) - 1` 制造了一个位数为 `maximumBit` 的二进制数，其中所有位都是1。这是因为 `1 << maximumBit` 产生了一个在第 `maximumBit` 位是1其余都是0的数，然后减1后，从第0位到第 `maximumBit-1` 位全变为1。这样的数是 `maximumBit` 位可以表示的最大数字，因此它确保了 `k` 的值可以取到任何小于 `2^maximumBit` 的数字，覆盖了所有可能的情况。

在题解的过程中，数组 `ans` 从头到尾记录了对应每个前缀数组的最大异或值。但题目要求是在每次操作中删除数组的最后一个元素，然后求剩余数组的最大异或值。这意味着数组的最后一个元素对应的最大异或值应该首先被计算，随着元素逐个被删除，前缀异或和的计算顺序与题目要求的删除顺序相反。因此，为了符合题目的要求，需要将 `ans` 数组进行反转，使得每一步的计算结果符合逐步删除数组元素的顺序。