题目描述

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

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

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

样例

输入：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。

输入：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。

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

限制

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

算法

(贪心) $O(n)$

1. 对于每个前缀异或和 $cur$，最终最大化的结果一定是 $m = 2^{maximumBit} - 1$，所以当前的答案为 $m \text{ XOR } (cur \text{ AND } m)$。
2. 此题和有序性没有关系。

时间复杂度

• 对于每个前缀异或和，仅需要常数的时间求解，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储答案。

C++ 代码

class Solution {
public:
    vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {
        const int n = nums.size();
        vector<int> ans;

        int cur = 0, m = (1 << maximumBit) - 1;
        for (int i = 0; i < n; i++)
            cur ^= nums[i];

        for (int i = n - 1; i >= 0; i--) {
            ans.push_back(m ^ (cur & m));
            cur ^= nums[i];
        }

        return ans;
    }
};