[LeetCode]1734. Decode XORed Permutation

题目

There is an integer array perm that is a permutation of the first n positive integers, where n is always odd.

It was encoded into another integer array encoded of length n - 1, such that encoded[i] = perm[i] XOR perm[i + 1]. For example, if perm = [1,3,2], then encoded = [2,1].

Given the encoded array, return the original array perm. It is guaranteed that the answer exists and is unique.

Example 1:

Input: encoded = [3,1]
Output: [1,2,3]
Explanation: If perm = [1,2,3], then encoded = [1 XOR 2,2 XOR 3] = [3,1]

Example 2:

Input: encoded = [6,5,4,6]
Output: [2,4,1,5,3]

Constraints:

• 3 <= n < 105
• n is odd.
• encoded.length == n - 1

XOR 性质

异或运算

异或是一种基于二进制的位运算，用符号XOR或者 ^ 表示，其运算法则是对运算符两侧数的每一个二进制位，同值取0，异值取1。它与布尔运算的区别在于，当运算符两侧均为1时，布尔运算的结果为1，异或运算的结果为0。

性质

1、交换律

2、结合律（即 (a^b)^c == a^(b^c) ）

3、对于任何数x，都有 x^x=0，x^0=x

4、自反性 A^B^B = A^0 = A

解题思路

由异或性质可知，任何一个数字异或它自己都等于0。也就是说，如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现一次的数字，因为那些出现两次的数字全部在异或中抵消掉了。用表达式来说就是 a ^ b ^ c ^ b ^ c = a, b 和 c都被抵消了，最后只剩下一个a。这启发我们如果要获取a，可以构造出 (b ^ c) 和 (a ^ b ^ c) 。

以Example2为例，记output[...] -> [a0, a1, a2, a3, a4], encoded[...] -> [e0, e1, e2, e3]，我们知道有：

• a0 ^ a1 = e0
• a1 ^ a2 = e1
• a2 ^ a3 = e2
• a3 ^ a4 = e3

如果我们知道第一个元素a0， 我们可以通过计算 a0 ^ e0 = a0 ^ (a0 ^ a1) = a1，来获取a1，同理我们可以借助 a1、e1 获取a2， 继而算出整个排列。

这样我们的问题就变成了求解a0。

考虑 :

• s1 = a0 ^ a1 ^ a2 ^ a3 ^ a4,
• s2 = a1 ^ a2 ^ a3 ^ a4 = e1 ^ e3

可以得出 s1 ^ s2 = (a0 ^ a1 ^ a2 ^ a3 ^ a4) ^ (a1 ^ a2 ^ a3 ^ a4) = a0 ！！！

也就是说我们先计算出从1 到 n 的异或值s1，然后再计算出encoded数列的奇数项异或值s2，再计算s1 ^ s2 结果就是 a0 了，由 a0 我们便可求出整个排列。

代码

/**
 * https://leetcode.com/problems/decode-xored-permutation/
 * author: deardeer
 */
class Solution {
public:
    vector<int> decode(vector<int>& encoded) {
        int sz = encoded.size();
        int n = sz + 1;
        int a0 = n;
        for(int i = 1; i < n; ++i) a0 ^= i; // 计算 s1
        for(int i = 1; i < sz; i += 2) { //计算 s1 ^ s2
            a0 ^= encoded[i]; 
        }

        vector<int> perm{a0};
        for(int i : encoded) perm.push_back(perm.back() ^ i); // 推算排列
        return perm;
    }
};