LC 1734. 解码异或后的排列

题目描述

这是 LeetCode 上的 1734. 解码异或后的排列 ，难度为 中等。

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

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

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

示例 1：

输入：encoded = [3,1]

输出：[1,2,3]

解释：如果 perm = [1,2,3] ，那么 encoded = [1 XOR 2,2 XOR 3] = [3,1]

示例 2：

输入：encoded = [6,5,4,6]

输出：[2,4,1,5,3]

提示：

• 3 <= n < $10^5$
• n 是奇数。
• encoded.length == n - 1

---

基本分析

我们知道异或运算有如下性质：

1. 相同数值异或，结果为 $0$
2. 任意数值与 $0$ 进行异或，结果为数值本身
3. 异或本身满足交换律

本题与 1720. 解码异或后的数组 的主要区别是没有给出首位元素。

因此，求得答案数组的「首位元素」或者「结尾元素」可作为本题切入点。

---

数学 & 模拟

我们定义答案数组为 ans[]，ans[] 数组的长度为 n，且 n 为奇数。

即有 $[ans[0], ans[1], ans[2], … , ans[n - 1]]$。

给定的数组 encoded[] 其实是 $[ans[0] ⊕ ans[1], ans[1] ⊕ ans[2], … , ans[n - 3] ⊕ ans[n - 2], ans[n - 2] ⊕ ans[n - 1]]$，长度为 n - 1。

由于每相邻一位会出现相同的数组成员 ans[x]，考虑“每隔一位”进行异或：

1. 从 encoded[] 的第 $0$ 位开始，每隔一位进行异或：可得 $ans[0] ⊕ ans[1] ⊕ … ⊕ ans[n - 2]$，即除了 ans[] 数组中的 $ans[n - 1]$ 以外的所有异或结果。

2. 利用 ans[] 数组是 n 个正整数的排列，我们可得 $ans[0] ⊕ ans[1] ⊕ … ⊕ ans[n - 2] ⊕ ans[n - 1]$，即 ans[] 数组中所有元素的异或结果。

将两式进行「异或」，可得 $ans[n - 1]$。

有了结尾元素后，问题变为与 1720. 解码异或后的数组 类似的模拟题。

代码：

class Solution {
    public int[] decode(int[] encoded) {
        int n = encoded.length + 1;
        int[] ans = new int[n];
        // 求得除了 ans[n - 1] 的所有异或结果
        int a = 0;
        for (int i = 0; i < n - 1; i += 2) a ^= encoded[i];
        // 求得 ans 的所有异或结果
        int b = 0;
        for (int i = 1; i <= n; i++) b ^= i;
        // 求得 ans[n - 1] 后，从后往前做
        ans[n - 1] = a ^ b;
        for (int i = n - 2; i >= 0; i--) {
            ans[i] = encoded[i] ^ ans[i + 1];
        }
        return ans;
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：构建同等数量级的答案数组。复杂度为 $O(n)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1734 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。