位运算题目：解码异或后的排列

题目

标题和出处

标题：解码异或后的排列

出处：1734. 解码异或后的排列

难度

6 级

题目描述

要求

有一个整数数组 $\text{perm}$，是前 $\text{n}$ 个正整数的排列，且 $\text{n}$ 是奇数。

它被加密成另一个长度为 $\text{n}-\text{1}$ 的整数数组 $\text{encoded}$，满足 $\text{encoded[i] = perm[i]}\oplus \text{perm[i + 1]}$。例如，如果 $\text{perm = [1,3,2]}$，那么 $\text{encoded = [2,1]}$。

给定 $\text{encoded}$ 数组，返回原始数组 $\text{perm}$。题目保证答案存在且唯一。

示例

示例 1：

输入：$\text{encoded = [3,1]}$
输出：$\text{[1,2,3]}$
解释：如果 $\text{perm = [1,2,3]}$，那么 $\text{encoded = [1}\oplus \text{2,2}\oplus \text{3] = [3,1]}$。

示例 2：

输入：$\text{encoded = [6,5,4,6]}$
输出：$\text{[2,4,1,5,3]}$

数据范围

• $\text{3}\le \text{n}<{\text{10}}^{\text{5}}$
• $\text{n}$ 是奇数
• $\text{encoded.length}=\text{n}-\text{1}$

解法

思路和算法

对于 $0\le i<n-1$ 有 $\text{encoded}[i]=\text{perm}[i]\oplus \text{perm}[i+1]$，利用按位异或的性质可以得到 $\text{encoded}[i]\oplus \text{perm}[i]=\text{perm}[i+1]\oplus \text{perm}[i]\oplus \text{perm}[i]=\text{perm}[i+1]$。因此对于 $1\le i<n$ 有 $\text{perm}[i]=\text{encoded}[i-1]\oplus \text{perm}[i-1]$。如果可以知道 $\text{perm}[0]$ 的值，则可以解码得到完整的原始数组 $\text{perm}$。

由于数组 $\text{perm}$ 的长度 $n$ 是奇数，因此除了 $\text{perm}[0]$ 以外的剩余元素个数 $n-1$ 是偶数，数组 $\text{encoded}$ 的长度 $n-1$ 是偶数。可以在数组 $\text{encoded}$ 中寻找 $\frac{n-1}{2}$ 个元素，使得这些元素的异或结果为 $\text{perm}[1]$ 到 $\text{perm}[n-1]$ 的异或结果。

由于 $\text{encoded}[i]=\text{perm}[i]\oplus \text{perm}[i+1]$，因此计算 $\text{encoded}$ 的所有奇数下标处的元素的异或结果，记为 $\text{oddXor}$，则该异或结果为 $\text{encoded}$ 的 $\frac{n-1}{2}$ 个元素的异或结果，等于 $\text{perm}[1]$ 到 $\text{perm}[n-1]$ 的异或结果。

用 $\text{totalXor}$ 表示 $1$ 到 $n$ 的所有整数的异或结果，则 $\text{totalXor}=\text{oddXor}\oplus \text{perm}[0]$，利用按位异或的性质可以得到 $\text{totalXor}\oplus \text{oddXor}=\text{oddXor}\oplus \text{oddXor}\oplus \text{perm}[0]=\text{perm}[0]$，即 $\text{perm}[0]$ 的值等于 $\text{totalXor}$ 和 $\text{oddXor}$ 的异或结果。

得到 $\text{perm}[0]$ 的值之后，从 $i=1$ 到 $i=n-1$ 依次计算 $\text{perm}[i]$ 的值，即可得到原数组 $\text{perm}$，且原数组的结果唯一。

代码

class Solution {public int[] decode(int[] encoded) {int n = encoded.length + 1;int[] perm = new int[n];int totalXor = 0;for (int i = 1; i <= n; i++) {totalXor ^= i;}int oddXor = 0;for (int i = 1; i < n; i += 2) {oddXor ^= encoded[i];}perm[0] = totalXor ^ oddXor;for (int i = 1; i < n; i++) {perm[i] = encoded[i - 1] ^ perm[i - 1];}return perm;}
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\text{perm}$ 的长度。需要遍历 $1$ 到 $n$ 的所有整数计算总异或值，然后遍历长度为 $n-1$ 的数组 $\text{encoded}$ 两次得到原始数组 $\text{perm}$。

• 空间复杂度：$O(1)$。注意返回值不计入空间复杂度。