一起玩转算法：解码异或后的数组
场景描述
未知 整数数组 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]
思路分析
根据两个数异或的特性
- a ^ a = 0: 任意一个数异或自身等于0
- 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)
本文参与?腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2021-05-08，如有侵权请联系?cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录