Medium

题目描述

给你一个下标从 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 <= 10^5
  • 1 <= nums[i] <= 10^9

解题思路

这道题看起来需要遍历所有的三元组，时间复杂度为 O(n³)，但实际上可以通过数学推导大大简化。

关键思路：逐位分析

我们可以按位考虑问题。对于二进制的每一位，计算所有三元组在该位上的贡献，然后将结果合并。

对于第 k 位，设数组中该位为 1 的元素个数为 cnt1，为 0 的元素个数为 cnt0。

表达式 ((nums[i] | nums[j]) & nums[k]) 在第 k 位的值为 1，当且仅当：

  • nums[k] 的第 k 位为 1
  • nums[i] 或 nums[j] 至少有一个的第 k 位为 1

因此，对于固定的 k（第 k 位为 1），满足条件的 (i,j) 对数为：n² - cnt0²（总数减去 i,j 都为 0 的情况）。

由于有 cnt1 个这样的 k，所以第 k 位上值为 1 的三元组总数为：cnt1 × (n² - cnt0²)。

如果这个数是奇数，则该位对最终结果有贡献；如果是偶数，则该位的异或结果为 0。

更简单的观察：

通过进一步分析发现，最终答案就是数组所有元素的异或结果！这是因为在异或运算中，大部分项会相互抵消，只留下每个元素本身的贡献。

代码实现

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

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

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

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

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(1)

相关题目