题目描述
未知 整数数组 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
。可以证明答案存在并且是唯一的。
样例
输入: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]
输入: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
算法
(数学) $O(n)$
- 根据异或的性质,得到
arr[i + 1] = arr[i] XOR encoded[i]
,然后遍历解码。
时间复杂度
- 遍历一遍数组即可解码,故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的空间存储答案。
C++ 代码
class Solution {
public:
vector<int> decode(vector<int>& encoded, int first) {
const int n = encoded.size();
vector<int> ans(n + 1);
ans[0] = first;
for (int i = 1; i <= n; i++)
ans[i] = ans[i - 1] ^ encoded[i - 1];
return ans;
}
};