相邻值的按位异或

标签: 位运算 数组

难度: Medium

下标从 0 开始、长度为 n 的数组 derived 是由同样长度为 n 的原始 二进制数组 original 通过计算相邻值的 按位异或（⊕）派生而来。

特别地，对于范围 [0, n - 1] 内的每个下标 i ：

  • 如果 i = n - 1 ，那么 derived[i] = original[i] ⊕ original[0]
  • 否则 derived[i] = original[i] ⊕ original[i + 1]

给你一个数组 derived ，请判断是否存在一个能够派生得到 derived 的 有效原始二进制数组 original 。

如果存在满足要求的原始二进制数组，返回 true ；否则，返回 false 。

  • 二进制数组是仅由 0 和 1 组成的数组。

示例 1：

输入：derived = [1,1,0]
输出：true
解释：能够派生得到 [1,1,0] 的有效原始二进制数组是 [0,1,0] ：
derived[0] = original[0] ⊕ original[1] = 0 ⊕ 1 = 1 
derived[1] = original[1] ⊕ original[2] = 1 ⊕ 0 = 1
derived[2] = original[2] ⊕ original[0] = 0 ⊕ 0 = 0

示例 2：

输入：derived = [1,1]
输出：true
解释：能够派生得到 [1,1] 的有效原始二进制数组是 [0,1] ：
derived[0] = original[0] ⊕ original[1] = 1
derived[1] = original[1] ⊕ original[0] = 1

示例 3：

输入：derived = [1,0]
输出：false
解释：不存在能够派生得到 [1,0] 的有效原始二进制数组。

提示：

  • n == derived.length
  • 1 <= n <= 105
  • derived 中的值不是 0 就是 1 。

Submission

运行时间: 77 ms

内存: 20.6 MB

class Solution:
    def doesValidArrayExist(self, derived: List[int]) -> bool:
        xor = 0
        for d in derived:
            xor = xor ^ d
        return xor == 0

Explain

题解的核心思路是利用按位异或的性质来判断是否存在一个符合条件的原始数组。具体地，由于异或操作具有可逆性和自反性（即 a^a=0 且 a^0=a），对派生数组 `derived` 中的所有元素进行连续异或操作后，如果结果为0，说明原始数组 `original` 可能存在。这是因为在派生过程中的异或操作，如果从 `original` 数组派生出 `derived`，最终所有的项异或的结果应该是0。这是因为各个项的异或会在原始数组的首尾项上抵消，即 original[0] ⊕ original[n-1]，如果 `derived` 数组能够由某个数组派生而来，则这个结果必须为0。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def doesValidArrayExist(self, derived: List[int]) -> bool:
        xor = 0  # 初始化xor变量为0
        for d in derived:  # 遍历derived数组
            xor = xor ^ d  # 对当前元素和xor进行异或操作
        return xor == 0  # 如果最终的xor结果为0，则可能存在符合条件的原数组

Explore

这种方法只能证明存在一个可能的原始数组，但不能确保只有这一种可能。由于异或操作的性质，如果得到的结果是0，这意味着原数组的第一个元素和最后一个元素异或的结果为0（即两者相等），这是构造原始数组的一个必要条件。但是，这种方法不能确定具体的原始数组是什么，只能说明这样的数组存在可能性。也就是说，可能存在多个不同的原始数组都能产生相同的derived数组。

异或操作具有一些特殊的性质，其中包括：任何数与0进行异或都会得到它本身，任何数与自身异或的结果是0。在派生数组的构建规则中，除了最后一个元素外，每个元素都与其下一个元素进行异或。最后一个元素与第一个元素异或。这种方式的结果是，除了原数组的第一个元素和最后一个元素外，所有元素都会在异或中被抵消（每个元素都出现两次）。因此，如果所有derived的元素异或之后的结果为0，这说明原数组的第一个元素与最后一个元素异或后也为0，即它们相等。这是由原始数组派生出derived数组的必要条件，因此检查异或结果是否为0是验证可能性的关键步骤。

题解中的方法通过一个简单的循环遍历derived数组，对数组中的每个元素执行一次异或操作。因为每个元素只被访问和处理一次，所以这个算法的时间复杂度是O(n)，其中n是derived数组的长度。这意味着算法的执行时间与数组的大小成线性关系，算法效率较高，适合处理大数据量。