跳转至

2527. 查询数组异或美丽值

题目描述

给你一个下标从 0 开始的整数数组 nums 。

三个下标 i ，j 和 k 的 有效值 定义为 ((nums[i] | nums[j]) & nums[k]) 。

一个数组的 异或美丽值 是数组中所有满足 0 <= i, j, k < n  的三元组 (i, j, k) 的 有效值 的异或结果。

请你返回 nums 的异或美丽值。

注意：

  • val1 | val2 是 val1 和 val2 的按位或。
  • val1 & val2 是 val1 和 val2 的按位与。

 

示例 1：

输入：nums = [1,4]
输出：5
解释：
三元组和它们对应的有效值如下：
- (0,0,0) 有效值为 ((1 | 1) & 1) = 1
- (0,0,1) 有效值为 ((1 | 1) & 4) = 0
- (0,1,0) 有效值为 ((1 | 4) & 1) = 1
- (0,1,1) 有效值为 ((1 | 4) & 4) = 4
- (1,0,0) 有效值为 ((4 | 1) & 1) = 1
- (1,0,1) 有效值为 ((4 | 1) & 4) = 4
- (1,1,0) 有效值为 ((4 | 4) & 1) = 0
- (1,1,1) 有效值为 ((4 | 4) & 4) = 4 
数组的异或美丽值为所有有效值的按位异或 1 ^ 0 ^ 1 ^ 4 ^ 1 ^ 4 ^ 0 ^ 4 = 5 。

示例 2：

输入：nums = [15,45,20,2,34,35,5,44,32,30]
输出：34
解释：数组的异或美丽值为 34 。

 

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109

解法

方法一：位运算

我们首先考虑 $i$ 与 $j$ 不相等的情况，此时 $(nums[i] | nums[j]) \& nums[k]$ 与 $(nums[j] | nums[i]) \& nums[k]$ 的结果是相同的，两者的异或结果为 $0$。

因此，我们只需要考虑 $i$ 与 $j$ 相等的情况。此时 $(nums[i] | nums[j]) \& nums[k] = nums[i] \& nums[k]$，如果 $i \neq k$，那么与 $nums[k] \& nums[i]$ 的结果是相同的，这些值的异或结果为 $0$。

因此，我们最终只需要考虑 $i = j = k$ 的情况，那么答案就是所有 $nums[i]$ 的异或结果。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为数组的长度。

1
2
3
class Solution:
    def xorBeauty(self, nums: List[int]) -> int:
        return reduce(xor, nums)

1
2
3
4
5
6
7
8
9
class Solution {
    public int xorBeauty(int[] nums) {
        int ans = 0;
        for (int x : nums) {
            ans ^= x;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    int xorBeauty(vector<int>& nums) {
        int ans = 0;
        for (auto& x : nums) {
            ans ^= x;
        }
        return ans;
    }
};

1
2
3
4
5
6
func xorBeauty(nums []int) (ans int) {
    for _, x := range nums {
        ans ^= x
    }
    return
}

1
2
3
function xorBeauty(nums: number[]): number {
    return nums.reduce((acc, cur) => acc ^ cur, 0);
}

评论