1829-每个查询的最大异或值

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

找到一个非负整数 k < 2maximumBit ，使得 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 <= 105
1 <= maximumBit <= 20
0 <= nums[i] < 2maximumBit
nums 中的数字已经按升序排好序。

方法一：位运算

提示 1

我们用 \oplus 表示按位异或运算。

根据按位异或运算的性质 a \oplus b \oplus b = a，我们可以在 O(1) 的时间，根据上一次询问需要的异或前缀和，得到当前询问需要的异或前缀和。

为了方便叙述，我们将第 i 次询问对应的异或前缀和记为

\textit{xorsum}_i = \textit{nums}[0] \oplus \textit{nums}[1] \oplus \cdots \oplus \textit{nums}[n-1-i]

提示 2

我们需要挑选一个包含不超过 maximumBit 个二进制位的非负整数 k，使得 k \oplus \textit{xorsum 的值最大。由于题目保证了数组 nums 中的元素一定小于等于 2^\textit{maximumBit} - 1，你是否可以直接构造出 k 值？

思路与算法

首先我们可以通过

\textit{xorsum}_{i-1} = \textit{xorsum}_i \oplus \textit{nums}[n-1-i]

在 O(1) 的时间更新每一次询问需要的异或前缀和。

再者，由于数组 nums 的元素一定小于等于 2^\textit{maximumBit} - 1，而 2^\textit{maximumBit} - 1 是一个二进制表示全部为 1 的数，因此数组 nums 中的任意异或前缀和一定也小于等于 2^\textit{maximumBit} - 1。这样一来，我们令 k = \textit{xorsum} \oplus (2^\textit{maximumBit} - 1)，k \oplus \textit{xorsum 就可以得到最大值 2^\textit{maximumBit} - 1。

代码

[sol1-C++]class Solution {
public:
    vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {
        int n = nums.size();
        int mask = (1 << maximumBit) - 1;
        int xorsum = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());
        
        vector<int> ans;
        for (int i = n - 1; i >= 0; --i) {
            ans.push_back(xorsum ^ mask);
            xorsum ^= nums[i];
        }
        return ans;
    }
};

[sol1-Python3]class Solution:
    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:
        n = len(nums)
        mask = (1 << maximumBit) - 1
        xorsum = reduce(xor, nums)
        
        ans = list()
        for i in range(n - 1, -1, -1):
            ans.append(xorsum ^ mask)
            xorsum ^= nums[i]
        
        return ans

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。这里不包括存储返回答案需要的空间。