操作后的最大异或和

难度: Medium

给你一个下标从 0 开始的整数数组 nums 。一次操作中，选择任意非负整数 x 和一个下标 i ，更新 nums[i] 为 nums[i] AND (nums[i] XOR x) 。

注意，AND 是逐位与运算，XOR 是逐位异或运算。

请你执行 任意次 更新操作，并返回 nums 中所有元素最大逐位异或和。

示例 1：

输入：nums = [3,2,4,6]
输出：7
解释：选择 x = 4 和 i = 3 进行操作，num[3] = 6 AND (6 XOR 4) = 6 AND 2 = 2 。
现在，nums = [3, 2, 4, 2] 且所有元素逐位异或得到 3 XOR 2 XOR 4 XOR 2 = 7 。
可知 7 是能得到的最大逐位异或和。
注意，其他操作可能也能得到逐位异或和 7 。

示例 2：

输入：nums = [1,2,3,9,2]
输出：11
解释：执行 0 次操作。
所有元素的逐位异或和为 1 XOR 2 XOR 3 XOR 9 XOR 2 = 11 。
可知 11 是能得到的最大逐位异或和。

提示：

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁸

Submission

运行时间: 36 ms

内存: 25.4 MB

class Solution:
    def maximumXOR(self, nums: List[int]) -> int:
        return reduce(or_, nums)

Explain

此题解的核心思路是通过对数组中所有元素进行逐位或运算（OR操作）来寻找最大异或和。由于XOR运算的性质，任何数字与0进行异或运算结果仍是原数字。因此，通过选择合适的x值，可以将nums[i]的某些位设置为1（如果它们在异或操作中可以为1）。此题解巧妙地使用了OR运算来确保数组中所有可置为1的位都被设置为1，这是因为OR运算可以将任何位上至少有一个1的情况统一设置为1。这样，计算所有元素的OR结果就能得到所有元素经过最优异或操作后可能达到的最高位值。

时间复杂度: O(n)

空间复杂度: O(1)

from functools import reduce
from operator import or_

class Solution:
    def maximumXOR(self, nums: List[int]) -> int:
        # 使用reduce函数和逐位或运算来计算所有元素的最大异或和
        return reduce(or_, nums)

Explore

在这个问题中，我们的目标是通过适当的操作使数组中的元素达到最大的逐位异或和。利用XOR运算的性质，任何数与0的异或结果仍然是原数。这意味着，通过适当选择x值，我们可以将nums[i]的某些位设为1（如果它们可以通过XOR操作变为1）。OR操作是最佳选择，因为它可以将多个数字中任何位置上的1合并起来显示在结果中。通过对所有数字进行OR操作，我们确保所有可能为1的位置在结果中都是1，从而达到最大异或和。这种方法不仅直接而且效率高，因为只需要一次遍历所有元素，并执行OR运算。

在本问题中，进行reduce(or_, nums)操作之前，对nums数组进行排序或去重是不必要的。OR运算是针对二进制位的操作，独立于元素的顺序，即运算的结果与元素的排列顺序无关。同时，去重也不是必需的，因为重复的值在OR运算中并不会影响最终结果的正确性。因此，任何此类预处理既不会提高效率，也不会影响最终结果，进行直接的reduce(or_, nums)操作即可。

reduce函数在执行逐位或（OR）运算时通常效率是高的，尤其是当处理的操作（如OR）相对简单且可以快速在硬件级别上实现时。reduce通过迭代方式将操作应用于所有元素，从而将时间复杂度控制在O(n)，n是数组的长度。对于大数据集，这种方法仍然是有效的，因为它避免了复杂的逻辑和多余的内存使用，直接在累计结果和当前元素之间执行位运算。然而，当数据极大时，内存带宽和处理速度可能成为限制因素，此时考虑并行处理策略可能会进一步提高效率。