Skip to content

Latest commit

 

History

History
127 lines (90 loc) · 3.41 KB

File metadata and controls

127 lines (90 loc) · 3.41 KB

English Version

题目描述

给你一个下标从 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 <= 105
  • 0 <= nums[i] <= 108

解法

方法一:位运算

在一次操作中,我们可以把 nums[i] 更新为 nums[i] AND (nums[i] XOR x)。由于 $x$ 是任意非负整数,因此 $nums[i] \oplus x$ 的结果是一个任意值,再与 nums[i] 逐位与运算,可以把 nums[i] 的二进制表示中的若干位 $1$ 变为 $0$

而题目中要获取的是 nums 所有元素的最大逐位异或和,对于一个二进制位,只要在 nums 中存在一个元素对应的二进制位为 $1$,那么这个二进制位对于最大逐位异或和的贡献就是 $1$。因此答案就是 nums 中所有元素的逐位或运算的结果。

时间复杂度 $O(n)$,空间复杂度 $O(1)$。其中 $n$nums 的长度。

Python3

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

Java

class Solution {
    public int maximumXOR(int[] nums) {
        int ans = 0;
        for (int x : nums) {
            ans |= x;
        }
        return ans;
    }
}

C++

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

Go

func maximumXOR(nums []int) (ans int) {
	for _, x := range nums {
		ans |= x
	}
	return
}

TypeScript

function maximumXOR(nums: number[]): number {
    let ans = 0;
    for (const x of nums) {
        ans |= x;
    }
    return ans;
}

...