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:

1
2
3
4
5
输入:encoded = [3,1]

输出:[1,2,3]

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

示例 2:
1
2
3
输入: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. 解码异或后的数组 的主要区别是没有给出首位元素。

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


数学 & 模拟

我们定义答案数组为 ansans 数组的长度为 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. 解码异或后的数组 类似的模拟题。

Java 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int[] decode(int[] encoded) {
int n = encoded.length + 1;
int[] ans = new int[n];
// 求得除了 ans[n - 1] 的所有异或结果
int a = 0, b = 0;
for (int i = 0; i < n - 1; i += 2) a ^= encoded[i];
// 求得 ans 的所有异或结果
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;
}
}

C++ 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
vector<int> decode(vector<int>& encoded) {
int n = encoded.size() + 1;
vector<int> ans(n);
// 求得除了 ans[n - 1] 的所有异或结果
int a = 0, b = 0;
for (int i = 0; i < n - 1; i += 2) a ^= encoded[i];
// 求得 ans 的所有异或结果
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;
}
};

Python 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def decode(self, encoded: List[int]) -> List[int]:
n = len(encoded) + 1
ans = [0] * n
# 求得除了 ans[n - 1] 的所有异或结果
a, b = 0, 0
for i in range(0, n - 1, 2):
a ^= encoded[i]
# 求得 ans 的所有异或结果
for i in range(1, n + 1):
b ^= i
# 求得 ans[n - 1] 后,从后往前做
ans[n - 1] = a ^ b
for i in range(n - 2, -1, -1):
ans[i] = encoded[i] ^ ans[i + 1]
return ans

TypeScript 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
function decode(encoded: number[]): number[] {
const n = encoded.length + 1;
const ans = new Array(n).fill(0);
// 求得除了 ans[n - 1] 的所有异或结果
let a = 0, b = 0;
for (let i = 0; i < n - 1; i += 2) a ^= encoded[i];
// 求得 ans 的所有异或结果
for (let i = 1; i <= n; i++) b ^= i;
// 求得 ans[n - 1] 后,从后往前做
ans[n - 1] = a ^ b;
for (let 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 原题链接和其他优选题解。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!