1720. 解码异或后的数组

川长思鸟来 2023-01-18 14:26 142阅读 0赞

> 困难题我唯唯诺诺，简单题我重拳出击

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjUxOTA0_size_16_color_FFFFFF_t_70]  
题目看着有点复杂，简单解释就是通过给出的公式  
`encoded[i] = arr[i] XOR arr[i + 1]`，arr数组，其中encoded\[\] 为已知，arr\[0\] 为已知，算出arr\[\]。其实所以我们要推导出arr\[i\] = ?? 这么一个公式。

在推导前我们先复习一下异或的相关特点:

1.  相同数值异或，结果为 0

x ^ x = 0

1.  任意数值与 0 进行异或，结果为数值本身

x ^ 0 = x

1.  异或本身满足交换律

a ^ b = b ^ a

更具上面的三个特征我们在根据`encoded[i-1] = arr[i-1] XOR arr[i]`进行推导

1.  首先将等式两边同时加上异或`arr[i-1]`,则等式变为如下

encoded[i-1] XOR arr[i-1] = arr[i-1] XOR arr[i] XOR arr[i-1]

1.  由性质3得

encoded[i-1] XOR arr[i-1] = arr[i-1] XOR arr[i-1] XOR arr[i]

1.  由性质1知

encoded[i-1] XOR arr[i-1] = 0 XOR arr[i]

1.  由性质二知

arr[i]  = encoded[i-1] XOR arr[i-1]

至此推导出了我们想要的公式：`arr[i] = encoded[i-1] XOR arr[i-1]`

实现代码如下：

public int[] decode(int[] encoded, int first) { 
            int n = encoded.length + 1;
            int[] ans = new int[n];
            ans[0] = first;
            for (int i = 1; i < n; i++) { 
                ans[i] = ans[i - 1] ^ encoded[i - 1];
            }
            return ans;
        }

*  时间复杂度: O(n), n 为encode数组的长度
 *  空间复杂度: O(n), 返回的结果数组也算的话
 *  [参考][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjUxOTA0_size_16_color_FFFFFF_t_70]: /images/20221021/383d1175f1b34275866a62c75d85e305.png
[Link 1]: https://leetcode-cn.com/problems/decode-xored-array/solution/gong-shui-san-xie-li-yong-yi-huo-xing-zh-p1bi/