每日一题：解码异或后的排列

题意

给你一个整数数组 $g$，它是前 $n$ 个正整数的排列，且 $n$ 是个 奇数 。

它被加密成另一个长度为 $n - 1$ 的整数数组 $a$ ，满足 $a[i] = g[i]$ ^ $g[i + 1]$。比方说，如果 $g = [1,3,2]$，那么 $a = [2,1]$。

给你 $a$ 数组，请你返回原始数组 $g$。题目保证答案存在且唯一。

Solution

可以发现如果对 $a$ 数组做前缀异或和得到 $sum$ 数组，那么 $sum[i]$ 就表示 $g[0]$ ^ $g[i + 1]$ 的值。$n$ 恰好为奇数，因此如果将数组 $sum$ 全部异或起来，$g[0]$ 刚好为被异或偶数次而抵消，得到的结果为 $g[1]$ ^ $g[2]$ ^ … ^ $g[n]$，恰好只有 $g[0]$ 没有出现。然后将这个结果与 $1-n$ 的所有数异或，得到的就是 $g[0]$ 的值，然后递推即可。时间复杂度 $O(n)$。

Code

class Solution {
public:
    vector<int> decode(vector<int>& a) {
        int n = a.size(), sum = 0;
        vector<int> g(n + 1);
        for (int i = 0; i < n; i++) g[0] ^= (sum ^= a[i]);
        for (int i = 1; i <= n + 1; i++) g[0] ^= i;
        for (int i = 0; i < n; i++) g[i + 1] = g[i] ^ a[i];
        return g;
    }
};