查询数组异或美丽值

标签: 位运算数组数学

难度: 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⁵
1 <= nums[i] <= 10⁹

Submission

运行时间: 31 ms

内存: 28.0 MB

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

Explain

这个题解直接计算了数组 `nums` 中所有元素的异或总和，忽略了题目中的复杂三元组运算条件。题目要求对于数组中的任意三元组 `(i, j, k)` 计算 `((nums[i] | nums[j]) & nums[k])` 的结果，并对所有这些结果进行异或。然而，这个题解仅仅对数组中的每个元素进行了异或运算，没有涉及到按位或和与运算。这表明题解可能误解了题目要求，或者是基于某种观察到的特性进行了简化处理，但没有在题解中提供这样的说明。

时间复杂度: O(n)

空间复杂度: O(1)

# 定义Solution类

class Solution:
    def xorBeauty(self, nums: List[int]) -> int:
        ans = 0  # 初始化结果变量
        for el in nums:  # 遍历数组中的每个元素
            ans ^= el  # 对每个元素进行异或运算
        return ans  # 返回最终的异或结果

Explore

题解中提到的直接对数组元素进行异或操作与题目要求的三元组运算实际上并无直接关联。题目中的三元组运算涉及到先进行按位或运算然后再进行与运算，这与简单的数组元素异或是两种完全不同的逻辑。题解中的处理可能是基于对题目的误解，或者是作者在没有明确说明的情况下对题目进行了过度简化。

题解中没有考虑所有可能的三元组 `(i, j, k)` 组合。正确的处理应该是考虑数组中的每一种可能的 `(i, j, k)` 组合，并计算每组的 `((nums[i] | nums[j]) & nums[k])` 值，最后对这些值进行异或运算以得到最终的异或美丽值。题解中仅考虑了对数组元素的简单异或，忽略了三元组的生成和相关的按位或与运算，因此无法正确反映题目的要求。

题解中的简化处理方式没有在文本中提供明确的理论依据或特定假设来支持其结果的正确性。基于题目描述和逻辑要求，简单地对数组元素进行异或运算并不能正确反映题目的复杂运算需求，因此这种处理方式在没有额外信息的情况下是不正确的。