Medium

题目描述

给你一个长度为 n 的整数数组 pref。找到并返回长度为 n 的数组 arr，满足：

pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]

注意 ^ 表示按位异或操作。

可以证明答案是唯一的。

示例 1：

输入：pref = [5,2,0,3,1]
输出：[5,7,2,3,2]
解释：从数组 [5,7,2,3,2] 我们有：
- pref[0] = 5
- pref[1] = 5 ^ 7 = 2
- pref[2] = 5 ^ 7 ^ 2 = 0
- pref[3] = 5 ^ 7 ^ 2 ^ 3 = 3
- pref[4] = 5 ^ 7 ^ 2 ^ 3 ^ 2 = 1

示例 2：

输入：pref = [13]
输出：[13]
解释：我们有 pref[0] = arr[0] = 13

约束条件：

  • 1 <= pref.length <= 10^5
  • 0 <= pref[i] <= 10^6

提示：

  • 考虑以下等式：x ^ a = b。如何找到 x？
  • 注意 arr[i] ^ pref[i-1] = pref[i]。这与前一个等式相同。

解题思路

解题思路

这道题的核心是理解异或运算的性质。已知前缀异或数组 pref，要求原数组 arr。

关键洞察： 由于 pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]，我们可以得到：

  • pref[0] = arr[0] → arr[0] = pref[0]
  • pref[1] = arr[0] ^ arr[1] → arr[1] = pref[1] ^ pref[0]
  • pref[i] = arr[0] ^ ... ^ arr[i-1] ^ arr[i] = pref[i-1] ^ arr[i]

因此：arr[i] = pref[i] ^ pref[i-1] (当 i > 0 时)

异或性质回顾：

  • a ^ a = 0
  • a ^ 0 = a
  • a ^ b = b ^ a（交换律）
  • 如果 a ^ b = c，那么 a = b ^ c

算法步骤：

  1. 第一个元素：arr[0] = pref[0]
  2. 其余元素：arr[i] = pref[i] ^ pref[i-1]

时间复杂度 O(n)，空间复杂度 O(1)（不算输出数组）。

这是一个经典的位运算应用，利用异或的自反性质巧妙地从前缀异或还原原数组。

代码实现

class Solution {
public:
    vector<int> findArray(vector<int>& pref) {
        int n = pref.size();
        vector<int> arr(n);
        
        arr[0] = pref[0];
        for (int i = 1; i < n; i++) {
            arr[i] = pref[i] ^ pref[i - 1];
        }
        
        return arr;
    }
};

class Solution:
    def findArray(self, pref: List[int]) -> List[int]:
        n = len(pref)
        arr = [0] * n
        
        arr[0] = pref[0]
        for i in range(1, n):
            arr[i] = pref[i] ^ pref[i - 1]
        
        return arr

public class Solution {
    public int[] FindArray(int[] pref) {
        int n = pref.Length;
        int[] arr = new int[n];
        
        arr[0] = pref[0];
        for (int i = 1; i < n; i++) {
            arr[i] = pref[i] ^ pref[i - 1];
        }
        
        return arr;
    }
}

/**
 * @param {number[]} pref
 * @return {number[]}
 */
var findArray = function(pref) {
    const n = pref.length;
    const arr = new Array(n);
    
    arr[0] = pref[0];
    for (let i = 1; i < n; i++) {
        arr[i] = pref[i] ^ pref[i - 1];
    }
    
    return arr;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(1)

说明：

  • 时间复杂度：需要遍历数组一次，对每个位置进行常数时间的异或运算
  • 空间复杂度：只使用了常数额外空间（不计算输出数组的空间）

相关题目