题目描述
给定一个整数数组 perm
,它是前 n
个正整数的排列,且 n
是个 奇数。
它被加密成另一个长度为 n - 1
的整数数组 encoded
,满足 encoded[i] = perm[i] XOR perm[i + 1]
。比方说,如果 perm = [1,3,2]
,那么 encoded = [2,1]
。
给定 encoded
数组,请你返回原始数组 perm
。题目保证答案存在且唯一。
样例
输入:encoded = [3,1]
输出:[1,2,3]
解释:如果 perm = [1,2,3] ,那么 encoded = [1 XOR 2,2 XOR 3] = [3,1]
输入:encoded = [6,5,4,6]
输出:[2,4,1,5,3]
限制
3 <= n < 10^5
n
是奇数。encoded.length == n - 1
算法
(数学) $O(n)$
- 先计算出 $1$ 到 $n$ 的异或和
tot
。 - 由于 $n$ 是奇数,所以通过
encoded
数组,可以推算出后 $n-1$ 个数字的异或和res
。 tot XOR res
就是第一个数字的值。- 然后根据第一个数字的值反推出所有的数字。
时间复杂度
- 异或求和,遍历数组两次,故总时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
vector<int> decode(vector<int>& encoded) {
const int n = encoded.size() + 1;
int tot = 0, res = 0;
for (int i = 1; i <= n; i++)
tot ^= i;
for (int i = 1; i < n - 1; i += 2)
res ^= encoded[i];
vector<int> ans(n);
ans[0] = res ^ tot;
for (int i = 1; i < n; i++)
ans[i] = ans[i - 1] ^ encoded[i - 1];
return ans;
}
};