一起玩转算法：解码异或后的数组

场景描述

未知 整数数组 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 。可以证明答案存在并且是唯一的。

示例：

输入：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]

思路分析

根据两个数异或的特性

1. a ^ a = 0: 任意一个数异或自身等于0
2. a ^ 0 = a: 任意一个数与0异或等于自身

再结合异或的交换与结合律，可以得出

encoded[i] = result[i] ^ result[i + 1]
encoded[i] ^ result[i] = result[i] ^ result[i] ^ result[i + 1]
encoded[i] ^ result[i] = result[i + 1]

所以要求源数组，我们得出的结论是：

result[0] = first
result[i+1] = result[i] ^ encoded[i] (i >= 0)

实现源码

    fun decode(encoded: IntArray, first: Int): IntArray {
        val result = IntArray(encoded.size + 1)
        result[0] = first
        encoded.forEachIndexed { index, i ->
            result[index + 1] = i.xor(result[index])
        }
        return result
    }

复杂度分析

• 时间复杂度：O(n), 其中n是原数组arr的长度
• 空间复杂度：O(1)