找出前缀异或的原始数组

记牢这一句口诀:arr[i] 等于 pref[i-1] 异或 pref[i]。异或有个好脾气,一个数和自己异或等于 0,所以相邻两个前缀里公共的部分全抵消了,只剩当前项。下面先把这条抵消关系看清楚,再逐位还原。

先认识 pref · 它是 arr 的前缀异或：舞台上这一行就是已知的 pref。它的每一位,都是原始数组 arr 从第 0 位一路异或到这一位的结果。比如 pref[3] 就是 arr[0]^arr[1]^arr[2]^arr[3]。现在 arr 是未知的,我们手上只有这行 pref,任务是把 arr 一位一位倒推回来。

关键:相邻两项一异或,公共段全抵消：看这两格。pref[1] 里含着 arr[0] 和 arr[1],pref[0] 就是 arr[0]。把这两个前缀异或一下,arr[0] 出现了两次,按位异或里一个数和自己相遇就变 0,于是 arr[0] 被消掉,只剩下 arr[1]。这就是还原的全部秘密:相邻两项一异或,公共的一大段全没了,精准留下当前这一项。

首项特殊:前面没有元素,虚拟前缀 0：第 0 位有点特殊,它前面没有 pref[-1] 可用。不过任何数异或 0 都等于它自己,所以我们给它补一个虚拟前缀 0,arr[0] 就等于 0 异或 pref[0],也就是 pref[0] 本身。这样首项和后面所有项就能用同一条公式统一处理了。这里 arr[0] 直接就是 5。

求 arr[0] · 收入面板：把第 0 位的结果正式收进右边的面板。arr[0] 等于 pref[0],等于 5。右侧这张表就是我们逐步搭出来的答案数组,先记下第一格 arr[0] 等于 5,接着往后一位一位求。

求 arr[1] · 定位相邻两项：轮到第 1 位。紫色指针停在 pref[1]=2,左边这格是 pref[0]=5。按口诀,arr[1] 就等于这相邻两个前缀异或起来。前面已经还原好的部分标成了蓝色,右边面板里也已经躺着 1 个结果。这一步先把要异或的两格锁定,下一帧算出它。

拆成二进制 · 逐位异或看清楚：把这两个数拆成三位二进制看得更透。5 是 101,2 是 010。按位异或的规矩是:同一位上两个数字相同就写 0,不同就写 1。一位一位比下来,得到 111,换回十进制正是 7。异或就是这么算的,没有进位,各位互不干扰。

得出 arr[1] = 7 · 收入面板：算出来了,arr[1] 等于 5 异或 2,结果是 7。把它收进右边面板的第 1 格。到这里已经还原出 2 个数了。继续往后,指针右移一位。

求 arr[2] · 定位相邻两项：轮到第 2 位。紫色指针停在 pref[2]=0,左边这格是 pref[1]=2。按口诀,arr[2] 就等于这相邻两个前缀异或起来。前面已经还原好的部分标成了蓝色,右边面板里也已经躺着 2 个结果。这一步先把要异或的两格锁定,下一帧算出它。

得出 arr[2] = 2 · 收入面板：算出来了,arr[2] 等于 2 异或 0,结果是 2。把它收进右边面板的第 2 格。到这里已经还原出 3 个数了。继续往后,指针右移一位。

求 arr[3] · 定位相邻两项：轮到第 3 位。紫色指针停在 pref[3]=3,左边这格是 pref[2]=0。按口诀,arr[3] 就等于这相邻两个前缀异或起来。前面已经还原好的部分标成了蓝色,右边面板里也已经躺着 3 个结果。这一步先把要异或的两格锁定,下一帧算出它。

得出 arr[3] = 3 · 收入面板：算出来了,arr[3] 等于 0 异或 3,结果是 3。把它收进右边面板的第 3 格。到这里已经还原出 4 个数了。继续往后,指针右移一位。

求 arr[4] · 定位相邻两项：轮到第 4 位。紫色指针停在 pref[4]=1,左边这格是 pref[3]=3。按口诀,arr[4] 就等于这相邻两个前缀异或起来。前面已经还原好的部分标成了蓝色,右边面板里也已经躺着 4 个结果。这一步先把要异或的两格锁定,下一帧算出它。

拆成二进制 · 逐位异或看清楚：把这两个数拆成三位二进制看得更透。3 是 011,1 是 001。按位异或的规矩是:同一位上两个数字相同就写 0,不同就写 1。一位一位比下来,得到 010,换回十进制正是 2。异或就是这么算的,没有进位,各位互不干扰。

得出 arr[4] = 2 · 收入面板：算出来了,arr[4] 等于 3 异或 1,结果是 2。把它收进右边面板的第 4 格。到这里已经还原出 5 个数了。这也是最后一位,arr 全部求完。

反过来验证 · 把 arr 累加异或还原 pref：还原完不能拍脑袋就交卷,回头验一遍才踏实。方法是反着来:拿刚求出的 arr,从左往右做前缀异或。设一个累加器 acc 从 0 开始,每读一个 arr[i] 就异或进去,得到的结果应该正好等于 pref[i]。如果每一位都对得上,说明我们还原的 arr 是对的。

验证 pref[0] · acc = 0 ^ 5 = 5：验证第 0 位。把 arr[0]=5 异或进累加器,acc 从 0 变成 5。抬头看 pref[0] 正好是 5,两边一致。这说明 arr 的前 1 位异或起来确实等于 pref[0],还原是准的。继续验下一位。

验证 pref[1] · acc = 5 ^ 7 = 2：验证第 1 位。把 arr[1]=7 异或进累加器,acc 从 5 变成 2。抬头看 pref[1] 正好是 2,两边一致。这说明 arr 的前 2 位异或起来确实等于 pref[1],还原是准的。继续验下一位。

验证 pref[2] · acc = 2 ^ 2 = 0：验证第 2 位。把 arr[2]=2 异或进累加器,acc 从 2 变成 0。抬头看 pref[2] 正好是 0,两边一致。这说明 arr 的前 3 位异或起来确实等于 pref[2],还原是准的。继续验下一位。

验证 pref[3] · acc = 0 ^ 3 = 3：验证第 3 位。把 arr[3]=3 异或进累加器,acc 从 0 变成 3。抬头看 pref[3] 正好是 3,两边一致。这说明 arr 的前 4 位异或起来确实等于 pref[3],还原是准的。继续验下一位。

验证 pref[4] · acc = 3 ^ 2 = 1：验证第 4 位。把 arr[4]=2 异或进累加器,acc 从 3 变成 1。抬头看 pref[4] 正好是 1,两边一致。这说明 arr 的前 5 位异或起来确实等于 pref[4],还原是准的。五位全部验过,验证通过。

回放 · arr = [5, 7, 2, 3, 2]：整道题回放一遍。核心只有一条:相邻两个前缀异或一次,公共段全抵消,arr[i] 就等于 pref[i-1] 异或 pref[i],首项特殊,直接等于 pref[0]。我们逐位求出 arr = [5, 7, 2, 3, 2],又反向把它累加异或还原出了原始的 pref,首尾对得上。这就是最终答案。

边界想清:单元素时 arr 就是 pref、含 0 值照常异或、多元素逐位套 pref[i-1] ^ pref[i]。

面试重点:核心是异或相消得 arr[i]=pref[i-1]^pref[i]、答案唯一、时间 O(n) 空间 O(1)。