題目敘述
題目會給我們一個輸入陣列，陣列裡面存放的是每個元素做XOR之後的前綴累積值。
要求我們從累積值還原出原本的陣列元素值。XOR前綴累積值定義:
pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]
測試範例
Example 1:
Input: pref = [5,2,0,3,1]
Output: [5,7,2,3,2]
Explanation: From the array [5,7,2,3,2] we have the following:
- 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.
Example 2:
Input: pref = [13]
Output: [13]
Explanation: We have pref[0] = arr[0] = 13.
約束條件
Constraints:
1 <= pref.length <= 1050 <= pref[i] <= 106
演算法
其實這題同樣運用到XOR運算子Self inverse的性質
A ⊕ A = 0
依照題目定義
pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]
我們可以知道
pref[0] = arr[0] 恰好是首項
接著
pref[1] = arr[0] ^ arr[1] 利用Self inverse的性質
計算pref[1] ^ pref[0] = (arr[0] ^ arr[1]) ^ arr[0] = arr[1]
還原出第二項 arr[1]
同理類推
計算pref[2] ^ pref[1] = (arr[0] ^ arr[1] ^ arr[2]) ^ (arr[0] ^ arr[1] )= arr[2]
還原出第三項 arr[2]
可以歸納出一個規律
arr[i] = pref[i] & pref[i-1]
由這個規則，去還原原始陣列元素值即可。
程式碼
class Solution:
def findArray(self, pref: List[int]) -> List[int]:
# Utilize the property of self-inverse
# Self-inverse : A ⊕ A = 0
# This means that any value XOR’d with itself gives zero.
origin = [ pref[0] ]
for i in range(1, len(pref)):
origin.append( pref[i]^pref[i-1] )
return origin
複雜度分析
時間複雜度:
O( n ) 迴圈迭代長度為O(n)，和原本的陣列一樣長。
空間複雜度:
O( n ) out-of-place update創造了一個origin array，和原本的陣列長度一樣長。
關鍵知識點
學完這題之後，記得吸收沉澱一下，
回去複習 Single Number 和 Find the difference 這兩題喔，背後用到的都是同樣的觀念，也都用到 XOR 運算子 Self-inverse的成雙成對互相消去的特質。
Reference:
