Question

2433. 找出前缀异或的原始数组

English Version

题目描述

给你一个长度为 n 的 整数 数组 pref 。找出并返回满足下述条件且长度为 n 的数组_ _arr ：

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

注意 ^ 表示 按位异或（bitwise-xor）运算。

可以证明答案是 唯一 的。

 

示例 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 <= 105
• 0 <= pref[i] <= 106

解法

方法一：位运算

根据题意，我们有式子一：

$$ pref[i]=arr[0] \oplus arr[1] \oplus \cdots \oplus arr[i] $$

所以，也就有式子二：

$$ pref[i-1]=arr[0] \oplus arr[1] \oplus \cdots \oplus arr[i-1] $$

我们将式子一二进行异或运算，得到：

$$ pref[i] \oplus pref[i-1]=arr[i] $$

即答案数组的每一项都是前缀异或数组的相邻两项进行异或运算得到的。

时间复杂度 $O(n)$，其中 $n$ 为前缀异或数组的长度。忽略答案的空间消耗，空间复杂度 $O(1)$。

class Solution:
  def findArray(self, pref: List[int]) -> List[int]:
    return [a ^ b for a, b in pairwise([0] + pref)]

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

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

func findArray(pref []int) []int {
  n := len(pref)
  ans := []int{pref[0]}
  for i := 1; i < n; i++ {
    ans = append(ans, pref[i-1]^pref[i])
  }
  return ans
}

function findArray(pref: number[]): number[] {
  let ans = pref.slice();
  for (let i = 1; i < pref.length; i++) {
    ans[i] = pref[i - 1] ^ pref[i];
  }
  return ans;
}

impl Solution {
  pub fn find_array(pref: Vec<i32>) -> Vec<i32> {
    let n = pref.len();
    let mut res = vec![0; n];
    res[0] = pref[0];
    for i in 1..n {
      res[i] = pref[i] ^ pref[i - 1];
    }
    res
  }
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* findArray(int* pref, int prefSize, int* returnSize) {
  int* res = (int*) malloc(sizeof(int) * prefSize);
  res[0] = pref[0];
  for (int i = 1; i < prefSize; i++) {
    res[i] = pref[i - 1] ^ pref[i];
  }
  *returnSize = prefSize;
  return res;
}