解码异或后的数组

标签: 位运算 数组

难度: Easy

未知 整数数组 arr 由 n 个非负整数组成。

经编码后变为长度为 n - 1 的另一个整数数组 encoded ，其中 encoded[i] = arr[i] XOR arr[i + 1] 。例如，arr = [1,0,2,1] 经编码后得到 encoded = [1,2,3] 。

给你编码后的数组 encoded 和原数组 arr 的第一个元素 first（arr[0]）。

请解码返回原数组 arr 。可以证明答案存在并且是唯一的。

 

示例 1：

输入：encoded = [1,2,3], first = 1
输出：[1,0,2,1]
解释：若 arr = [1,0,2,1] ，那么 first = 1 且 encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]

示例 2：

输入：encoded = [6,2,7,3], first = 4
输出：[4,2,0,7,4]

 

提示：

  • 2 <= n <= 104
  • encoded.length == n - 1
  • 0 <= encoded[i] <= 105
  • 0 <= first <= 105

Submission

运行时间: 30 ms

内存: 17.4 MB

class Solution:
    def decode(self, encoded: List[int], first: int) -> List[int]:
        ans = [first]
        for i in encoded:
            ans.append(i ^ ans[-1])
        return ans

Explain

题解利用了异或操作的性质：一个数与另一个数异或两次后，结果仍然是原来的数。给定 encoded 数组和 first 元素，利用这个性质来逐个求出原数组 arr 的元素。首先将 first 添加到结果数组 ans 中，然后利用循环，每次从 encoded 数组取一个元素与 ans 中的最后一个元素进行异或操作，得到的结果即为原数组的下一个元素。这样逐步解码整个数组。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def decode(self, encoded: List[int], first: int) -> List[int]:
        # 初始化结果数组，包含了原数组的第一个元素
        ans = [first]
        # 遍历 encoded 数组，利用异或恢复原数组的下一个元素
        for i in encoded:
            # 将当前 encoded 元素与结果数组的最后一个元素异或，得到下一个原数组元素
            ans.append(i ^ ans[-1])
        # 返回解码后的原数组
        return ans

Explore

异或操作（XOR）有一个关键性质：任何数与自身异或的结果是0，即`b XOR b = 0`，并且任何数与0异或的结果是其自身，即`a XOR 0 = a`。利用这些性质，我们可以得到`a XOR b XOR b = a XOR (b XOR b) = a XOR 0 = a`。在题目中，如果我们知道原数组`arr`的某一个元素以及它与下一个元素的异或结果（即`encoded`数组中的对应元素），我们可以通过异或这个结果与已知的原数组元素来解出下一个原数组元素。这个性质使得我们能够从一个已知的元素（`first`）开始，逐步解码出整个原数组。

在解码过程中，每个原数组`arr`的元素都可以通过其前一个元素和`encoded`数组中相应的元素唯一确定。因为异或操作是可逆的，所以一旦给定第一个元素`first`（即`arr[0]`），我们可以使用`first`和`encoded[0]`来确定`arr[1]`，然后使用`arr[1]`和`encoded[1]`来确定`arr[2]`，以此类推。由于此过程中没有任何随机性或多种可能性，整个原数组`arr`可以唯一地由`first`和`encoded`数组确定。

如果`encoded`数组不完整或存在错误，当前的解码策略将无法正确工作，因为每个元素的解码都依赖于前一个元素和对应的`encoded`元素。一旦`encoded`数组丢失或错误，解码得到的后续元素也将是错误的。为了验证解码结果的正确性，如果原始的`arr`数组可用，可以通过重新计算每个连续元素对的异或并与`encoded`数组比较来进行验证。如果匹配，则解码结果正确。如果原始`arr`不可用，验证正确性将是困难的，除非有额外的信息或约束条件。

是的，应该考虑这些特殊情况。如果`encoded`为空数组，这意味着原数组`arr`仅包含一个元素，即`first`。在这种情况下，解码函数应直接返回包含单个元素`first`的数组。关于`first`的特殊值，虽然极大或极小值可能引起对整数溢出的考虑，但由于Python的整数类型可以自动处理较大数，通常不需要特别处理这些情况。然而，在其他编程语言中，可能需要考虑整数溢出的问题。