每个查询的最大异或

1829。每个查询的最大异或

难度：中等

主题：数组、位操作、前缀和

给你一个排序 n 个非负整数数组nums 和一个整数maximumBit。您想要执行以下查询 n 次:

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

返回数组答案，其中answer[i]是第i^第查询的答案。

示例1：

• 输入： nums = [0,1,1,3]，maximumBit = 2
• 输出： [0,3,2,3]
• 说明：问题解答如下：
  • 1^stst 查询：nums = [0,1,1,3], k = 0，因为 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3。
  • 2^nd 查询：nums = [0,1,1], k = 3 因为 0 XOR 1 XOR 1 XOR 3 = 3.
  • 3^rd 查询：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]
• 说明：问题解答如下：
  • 1^stst 查询：nums = [2,3,4,7], k = 5，因为 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7。
  • 2^nd 查询：nums = [2,3,4], k = 2 因为 2 XOR 3 XOR 4 XOR 2 = 7.
  • 3^rd 查询：nums = [2,3], k = 6 因为 2 XOR 3 XOR 6 = 7.
  • 4^第 查询：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 5
• 1
• 0 最大位
• nums​​​ 按升序顺序排序。

提示：

1. 请注意，最大可能的 XOR 结果始终为 2^{(maximumBit) - 1}
2. 因此前缀的答案是该前缀与 2^{(maximumBit)-1} 的异或

解决方案：

我们需要有效地计算数组中元素的异或，并使用值 k 最大化结果，使得 k 小于 2^maximumBit。解决这个问题的方法如下：

观察和方法

1. 最大化异或:
   我们可以与任何前缀和进行异或运算的最大位数是（2^{text{maximumBit}} - 1）。这是因为与多个全 1（即二进制的 111...1）进行异或总是会最大化结果。

2. 前缀异或计算:
   我们可以为整个数组维护一个累积的 XOR，而不是为每个查询重新计算 XOR。由于 XOR 具有 A XOR B XOR B = A 的属性，因此可以通过从累积 XOR 中异或出该元素来从数组中删除最后一个元素。

3. 算法:

   • 首先计算 nums 中所有元素的异或。我们称之为当前异或。
   • 对于每个查询（从最后一个到第一个）：
     • 通过将 currentXOR 与 maxNum 进行异或计算，其中 maxNum = 2^maximumBit - 1。
     • 将 k 追加到结果列表中。
     • 通过对 currentXOR 进行异或来从 nums 中删除最后一个元素。
   • 结果列表将以相反的顺序包含答案，因此最后将其颠倒过来。

让我们用 PHP 实现这个解决方案：1829。每个查询的最大异或

<?php
/**
 * @param Integer[] $nums
 * @param Integer $maximumBit
 * @return Integer[]
 */
function getMaximumXor($nums, $maximumBit) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$nums = [0,1,1,3];
$maximumBit = 2;
print_r(getMaximumXor($nums, $maximumBit));  // Output should be [0, 3, 2, 3]
?>

解释：

1. 计算 maxNum:

   • maxNum 的计算方式为 2^maximumBit - 1，即指定位长度的二进制全 1 的数字。

2. 初始异或计算:

   • 我们对 nums 中的所有元素进行异或，得到累积异或（currentXOR），代表数组中所有数字的异或。

3. 向后迭代:

   • 我们从 nums 中的最后一个元素开始，计算每一步的最大异或：
     • currentXOR ^ maxNum 给出当前状态的最大 k。
     • 将 k 添加到答案中。
   • 然后我们将 nums 的最后一个元素与 currentXOR 进行异或，以将其从下一次迭代的异或和中“删除”。

4. 返回答案：

   • 由于我们反向处理了列表，答案将包含相反顺序的值，因此最终列表已经根据我们的要求正确排列。

复杂性分析

• 时间复杂度：O(n)，因为我们在O(n)中计算初始异或，并且每个查询都会在恒定时间内处理。
• 空间复杂度：O(n)，用于存储答案。

这段代码很高效，应该很好地处理约束的上限。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是每个查询的最大异或的详细内容。更多信息请关注PHP中文网其他相关文章！