Medium

题目描述

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

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

返回对数组 nums 执行任意次操作后，nums 中所有元素逐位异或的 最大可能值 。

示例 1：

输入：nums = [3,2,4,6]
输出：7
解释：对 x = 4 和 i = 3 执行操作，nums[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^5
  • 0 <= nums[i] <= 10^8

解题思路

这道题的关键是理解操作的本质：nums[i] AND (nums[i] XOR x)。

让我们分析这个操作能做什么：

  • 对于 nums[i] 的任意一位，如果该位是1，我们可以选择合适的 x 使其变为0
  • 如果该位是0，无论如何操作都无法变为1

具体来说，假设 nums[i] 的某一位是1：

  • 如果 x 的对应位是1，则 nums[i] XOR x 的该位变为0，最终 nums[i] AND (nums[i] XOR x) 该位为0
  • 如果 x 的对应位是0，则 nums[i] XOR x 的该位仍为1，最终该位仍为1

因此，这个操作只能将某些位从1变为0，不能从0变为1。

要使最终的异或值最大，我们需要让尽可能多的位为1。对于第 k 位：

  • 如果数组中至少有一个数的第 k 位为1，我们就有可能让最终异或结果的第 k 位为1
  • 具体方法是：保持奇数个数的第 k 位为1，其余数的第 k 位置为0

因此，答案就是对数组中所有数进行按位或运算的结果。

代码实现

class Solution {
public:
    int maximumXOR(vector<int>& nums) {
        int result = 0;
        for (int num : nums) {
            result |= num;
        }
        return result;
    }
};

class Solution:
    def maximumXOR(self, nums: List[int]) -> int:
        result = 0
        for num in nums:
            result |= num
        return result

public class Solution {
    public int MaximumXOR(int[] nums) {
        int result = 0;
        foreach (int num in nums) {
            result |= num;
        }
        return result;
    }
}

var maximumXOR = function(nums) {
    let result = 0;
    for (let num of nums) {
        result |= num;
    }
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度数值
时间复杂度O(n)
空间复杂度O(1)

相关题目