题目描述
未知 整数数组 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
算法分析
- 由于
encoded[i] = arr[i] XOR arr[i + 1]
,当已知arr[i]
时,可以计算出arr[i + 1] = encode[i] XOR arr[i]
,也就是当知道arr
的前一个元素时,可以计算出后一个元素
时间复杂度 $O(n)$
Java 代码
class Solution {
public int[] decode(int[] encoded, int first) {
int n = encoded.length;
int[] arr = new int[n + 1];
arr[0] = first;
for(int i = 1;i <= n;i ++)
{
arr[i] = encoded[i - 1] ^ arr[i - 1];
}
return arr;
}
}