Medium

题目描述

给你一个由 n 个非负整数组成的数组 nums 和一个整数 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]
解释：查询的答案如下：
第 1 次查询：nums = [0,1,1,3], k = 0 因为 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3。
第 2 次查询：nums = [0,1,1], k = 3 因为 0 XOR 1 XOR 1 XOR 3 = 3。
第 3 次查询：nums = [0,1], k = 2 因为 0 XOR 1 XOR 2 = 3。
第 4 次查询：nums = [0], k = 3 因为 0 XOR 3 = 3。

示例 2：

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

示例 3：

输入：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 按升序排列

解题思路

这道题的关键在于理解异或运算的性质和如何获得最大异或值。

核心思路：

  1. 最大异或值的目标：我们希望得到的最大异或结果是 2^maximumBit - 1，即所有 maximumBit 位都为 1 的数。

  2. 异或性质利用：如果当前前缀的异或值为 prefix_xor，要使 prefix_xor XOR k 等于目标值 max_val，则 k = prefix_xor XOR max_val。

  3. 前缀异或的计算：我们可以预先计算所有前缀的异或值，然后从后往前处理每个查询。

  4. 逆向思考：由于每次都要移除最后一个元素，我们可以从完整数组开始，逐步移除元素，这样避免重复计算前缀异或。

算法步骤：

  • 计算整个数组的异或值
  • 对于每次查询，当前的 k 值 = 当前异或值 XOR (2^maximumBit - 1)
  • 移除最后一个元素（通过异或操作：当前异或值 XOR 最后元素）

时间复杂度为 O(n)，空间复杂度为 O(1)（不考虑输出数组）。

代码实现

class Solution {
public:
    vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {
        int n = nums.size();
        int maxVal = (1 << maximumBit) - 1;
        int xorAll = 0;
        
        // 计算整个数组的异或值
        for (int num : nums) {
            xorAll ^= num;
        }
        
        vector<int> answer(n);
        
        // 从后往前处理每个查询
        for (int i = 0; i < n; i++) {
            // 当前查询的答案
            answer[i] = xorAll ^ maxVal;
            // 移除最后一个元素
            xorAll ^= nums[n - 1 - i];
        }
        
        return answer;
    }
};

class Solution:
    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:
        n = len(nums)
        max_val = (1 << maximumBit) - 1
        xor_all = 0
        
        # 计算整个数组的异或值
        for num in nums:
            xor_all ^= num
        
        answer = []
        
        # 从后往前处理每个查询
        for i in range(n):
            # 当前查询的答案
            answer.append(xor_all ^ max_val)
            # 移除最后一个元素
            xor_all ^= nums[n - 1 - i]
        
        return answer

public class Solution {
    public int[] GetMaximumXor(int[] nums, int maximumBit) {
        int n = nums.Length;
        int maxVal = (1 << maximumBit) - 1;
        int xorAll = 0;
        
        // 计算整个数组的异或值
        foreach (int num in nums) {
            xorAll ^= num;
        }
        
        int[] answer = new int[n];
        
        // 从后往前处理每个查询
        for (int i = 0; i < n; i++) {
            // 当前查询的答案
            answer[i] = xorAll ^ maxVal;
            // 移除最后一个元素
            xorAll ^= nums[n - 1 - i];
        }
        
        return answer;
    }
}

var getMaximumXor = function(nums, maximumBit) {
    const n = nums.length;
    const maxVal = (1 << maximumBit) - 1;
    let xorAll = 0;
    
    // 计算整个数组的异或值
    for (const num of nums) {
        xorAll ^= num;
    }
    
    const answer = [];
    
    // 从后往前处理每个查询
    for (let i = 0; i < n; i++) {
        // 当前查询的答案
        answer.push(xorAll ^ maxVal);
        // 移除最后一个元素
        xorAll ^= nums[n - 1 - i];
    }
    
    return answer;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(1)

其中 n 为数组 nums 的长度。我们只需要遍历数组一次来计算初始异或值，然后再遍历一次来生成答案，因此时间复杂度为 O(n)。除了输出数组外，只使用了常数额外空间。

相关题目