1720. 解码异或后的数组

🟢   🔖  位运算 数组  🔗 力扣 LeetCode

题目

There is a hidden integer array arr that consists of n non-negative integers.

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

You are given the encoded array. You are also given an integer first, that is the first element of arr, i.e. arr[0].

Return the original array arr. It can be proved that the answer exists and is unique.

Example 1:

Input: encoded = [1,2,3], first = 1

Output: [1,0,2,1]

Explanation: If arr = [1,0,2,1], then first = 1 and encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]

Example 2:

Input: encoded = [6,2,7,3], first = 4

Output: [4,2,0,7,4]

Constraints:

• 2 <= n <= 10^4
• encoded.length == n - 1
• 0 <= encoded[i] <= 10^5
• 0 <= first <= 10^5

题目大意

未知 整数数组 arr 由 n 个非负整数组成。

经编码后变为长度为 n - 1 的另一个整数数组 encoded ，其中 encoded[i] = arr[i] XOR arr[i + 1] 。例如，arr = [1,0,2,1] 经编码后得到 encoded = [1,2,3] 。

给你编码后的数组 encoded 和原数组 arr 的第一个元素 first（arr[0]）。

请解码返回原数组 arr 。可以证明答案存在并且是唯一的。

示例 1：

输入： encoded = [1,2,3], first = 1

输出：[1,0,2,1]

解释： 若 arr = [1,0,2,1] ，那么 first = 1 且 encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]

示例 2：

输入： encoded = [6,2,7,3], first = 4

输出：[4,2,0,7,4]

提示：

• 2 <= n <= 10^4
• encoded.length == n - 1
• 0 <= encoded[i] <= 10^5
• 0 <= first <= 10^5

解题思路

异或运算的性质：

1. 自反性：
   • a ^ a = 0
   • a ^ 0 = a
2. 交换性和结合性：
   • a ^ b = b ^ a
   • (a ^ b) ^ c = a ^ (b ^ c)
3. 还原关系：
   • 如果 c = a ^ b，则 a = c ^ b，且 b = c ^ a。

根据性质 3，可以解码出原始数组。

已知：encoded[i] = res[i] ^ res[i+1]

因此： res[i+1] = encoded[i] ^ res[i]。

1. 初始时，将 first 放入 res。
2. 遍历 encoded，逐步根据 res[i+1] = encoded[i] ^ res[i] 解码。

复杂度分析

• 时间复杂度：O(n)，需要遍历一次 encoded。
• 空间复杂度：O(n)，结果数组 res 占用线性空间。

代码

/**
 * @param {number[]} encoded
 * @param {number} first
 * @return {number[]}
 */
var decode = function (encoded, first) {
	let res = [first]; // 初始化结果数组，包含第一个元素
	let prev = first; // 记录当前的前一个元素
	for (let num of encoded) {
		// 解码：res[i+1] = encoded[i] ^ res[i]
		prev = prev ^ num;
		res.push(prev);
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
2433	找出前缀异或的原始数组		位运算 数组	🟠	🀄️ 🔗