跳至主要內容

1720. 解码异或后的数组


1720. 解码异或后的数组

🟢   🔖  位运算 数组  🔗 力扣open in new window LeetCodeopen in new window

题目

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

题目大意

未知 整数数组 arrn 个非负整数组成。

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

给你编码后的数组 encoded 和原数组 arr 的第一个元素 firstarr[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找出前缀异或的原始数组位运算 数组🟠🀄️open in new window 🔗open in new window