Leetcode-1720-解码异或后的数组

Leetcode-1720-解码异或后的数组

题目描述

• 未知 整数数组 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

算法思路：异或性质

异或运算具有如下性质：

• 异或运算满足交换律和结合律；

• 任意整数和自身做异或运算的结果都等于 0，即x⊕x=0；

• 任意整数和 0 做异或运算的结果都等于其自身，即x⊕0=0⊕x=x。

题目要求：

性质分析

class Solution {
    public int[] decode(int[] encoded, int first) {
        // 1. 创建arr数组
        int n = encoded.length;
        int[] arr = new int[n + 1];
        arr[0] = first;

        // 2. 异或还原
        for(int i = 1;i <= n;++i){
            arr[i] = arr[i - 1] ^ encoded[i - 1];
        }

        // 3. 返回结果数组
        return arr;
    }
}

复杂度分析

• 时间复杂度 ：O(n) , 其中n是原数组的长度，原因是要遍历encoded数组一次
• 空间复杂度 ：O(1) 注意空间复杂度不考虑返回值。

打赏