解码异或排列的结果总是唯一的，这是真的吗？

Question

我正在努力完成 LeetCode 任务：解码异或排列

有一个整数数组 perm ，它是前 n 个的排列 正整数，其中 n 始终为奇数。

它被编码成另一个长度为 n - 1 的整数数组， 这样，encoded[i] = perm[i] XOR perm[i + 1]。例如，如果烫发 = [1,3,2]，然后编码 = [2,1]。

给定编码数组，返回原始数组 perm。这是 保证答案存在并且是唯一的。

我想这样解决：

1. 对编码数组的所有元素进行异或。就给它起个名字吧

   X

2. 对编码数组中位于偶数位置的元素进行异或（因此我删除了除结果排列数组中的第一个元素之外的所有元素）。就给它起个名字吧

   Y

3. 我做了

   X xor Y

   ，这是我排列数组中的第一个元素。

如果我知道第一个元素，我可以轻松解决整个问题。 这就是代码：

std::vector<int> decode(std::vector<int> encoded) {
    int xor_of_encoded = 0;
    int xor_without_known_elements = 0;
    for (int i = 0; i < encoded.size(); i++) {
        xor_of_encoded ^= encoded[i];
        if (i % 2 == 1)
            xor_without_known_elements ^= encoded[i];
    }

    std::vector<int> decoded(encoded.size() + 1);
    decoded[0] = xor_of_encoded ^ xor_without_known_elements;

    for (int i = 1; i <= encoded.size(); i++) {
        decoded[i] = (encoded[i - 1] ^ decoded[i - 1]);
    }

    return decoded;
}

其工作原理的直观表示：

   6   5   4   6         <-- encoded
   |   |   |   |
   Ʌ   Ʌ   Ʌ   Ʌ
  / \ / \ / \ / \
 |   V   V   V   |
 |   |   |   |   |
 2   4   1   5   3       <-- result

当我提交解决方案时，它通过了第二个测试用例：

[6,5,4,6]

。对于

[3,1]

和

[12,6,11,10,5,3,4,6]

以及可能对于其他情况，它都会失败，但我没有机会在其余情况下测试它。问题是我的代码产生的结果满足任务的假设。

当我手动对上述代码的结果进行异或时（

decoded[i] xor decoded[i+1]

，这就是任务中提到的编码数组的创建方式），我能够重新创建编码数组。

所以我对这个问题很困惑。我是否运气很好或错过了什么，或者结果不是唯一的？

Answer 1

假设输入长度为n。

• 求 1 到 n 的异或
• 找到编码数组的每个奇数元素的异或（0索引，即跳过第一个elt以及此后的所有其他元素）
• 求前两个结果的异或。这是第一个元素。

现在您有了第一个元素，请使用异或来查找所有其他元素。

例如

arr = [4,2,1,3,5]
encoded = [6, 3, 2, 6] 
xor of 1 upto 5 = 1^2^3^4^5 = 1
xor of odd encoded = 3 ^ 6 = 5
xor of two prev = 1^5 = 4 = first elt of input arr

然后我们使用连续编码元素的异或得到其余部分：

4^6 = 2
2^3 = 1
1^2 = 3
3^6 = 5