Easy

题目描述

存在一个由 n 个非负整数组成的整数数组 arr 。

它被编码成另一个长度为 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 <= 10^4
  • encoded.length == n - 1
  • 0 <= encoded[i] <= 10^5
  • 0 <= first <= 10^5

解题思路

这道题考查的是异或运算的性质。

核心思路： 由于 encoded[i] = arr[i] XOR arr[i+1]，我们可以利用异或运算的性质来逆推原数组。

关键性质： 如果 a XOR b = c，那么 a XOR c = b 和 b XOR c = a。

解题步骤：

  1. 已知 arr[0] = first
  2. 由于 encoded[0] = arr[0] XOR arr[1]，所以 arr[1] = encoded[0] XOR arr[0]
  3. 类似地，arr[2] = encoded[1] XOR arr[1]
  4. 依此类推，可以得到通用公式：arr[i+1] = encoded[i] XOR arr[i]

算法流程：

  1. 初始化结果数组，第一个元素为 first
  2. 从 i = 0 开始遍历 encoded 数组
  3. 利用公式 arr[i+1] = encoded[i] XOR arr[i] 计算下一个元素
  4. 重复直到计算出所有元素

时间复杂度为 O(n)，空间复杂度为 O(n)（用于存储结果）。

代码实现

class Solution {
public:
    vector<int> decode(vector<int>& encoded, int first) {
        vector<int> result;
        result.push_back(first);
        
        for (int i = 0; i < encoded.size(); i++) {
            result.push_back(encoded[i] ^ result[i]);
        }
        
        return result;
    }
};

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

public class Solution {
    public int[] Decode(int[] encoded, int first) {
        int[] result = new int[encoded.Length + 1];
        result[0] = first;
        
        for (int i = 0; i < encoded.Length; i++) {
            result[i + 1] = encoded[i] ^ result[i];
        }
        
        return result;
    }
}

var decode = function(encoded, first) {
    const result = [first];
    
    for (let i = 0; i < encoded.length; i++) {
        result.push(encoded[i] ^ result[i]);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历一次 encoded 数组，n 为原数组长度
空间复杂度O(n)需要额外空间存储结果数组

相关题目