解題說明
Decode XORed Array
題目描述:已知一個長度為 n 的整數陣列 arr(原始),現在有一個長度為 n-1 的 encoded 陣列,其中 encoded[i] = arr[i] XOR arr[i+1]。另外給定 arr[0] = first(第一個元素的值)。請解碼並回傳原始陣列 arr。
解題思路:利用 XOR 的關鍵性質:a XOR b = c 則 a XOR c = b(自反性)。
已知 encoded[i] = arr[i] XOR arr[i+1],兩邊同時與 arr[i] 做 XOR:
arr[i] XOR encoded[i] = arr[i] XOR arr[i] XOR arr[i+1] = 0 XOR arr[i+1] = arr[i+1]
因此 arr[i+1] = arr[i] XOR encoded[i]。從已知的 arr[0] = first 出發,逐步計算 arr[1], arr[2], ...,線性掃描一遍即可還原完整陣列。
C++ 解法
複雜度分析
時間複雜度:O(n)——只需一次線性掃描 encoded 陣列(長度 n-1),每步做一次 XOR 運算(O(1)),整體為 O(n)。
空間複雜度:O(n)——輸出陣列 arr 長度為 n;若不計輸出空間,額外空間為 O(1)(只用到幾個整數變數)。
虛擬碼
1. Initialize arr of size n = len(encoded) + 1. 2. Set arr[0] = first. 3. For i from 0 to len(encoded) - 1: a. arr[i+1] = arr[i] XOR encoded[i]. 4. Return arr.
其他解法
方法一:前綴 XOR 計算
定義前綴 XOR prefix[k] = arr[0] XOR arr[1] XOR ... XOR arr[k]。由 encoded[i] = arr[i] XOR arr[i+1],可推出 encoded[0] XOR encoded[1] XOR ... XOR encoded[i-1] = arr[0] XOR arr[i],故 arr[i] = first XOR (encoded[0] XOR ... XOR encoded[i-1])。可先建構 encoded 的前綴 XOR 陣列,再一次計算所有 arr[i],時間空間同為 O(n),但需兩次掃描,略遜於直接遞推。
方法二:原地計算(In-place,若允許修改 encoded)
若允許修改 encoded,可擴展其長度為 n,在 encoded 陣列前插入 first,然後原地利用 encoded[i] ^= encoded[i-1] 轉換為前綴 XOR,即為答案。節省額外空間但修改了輸入,一般面試中不推薦。
方法三:反向解碼
若另外給定 arr[n-1](最後一個元素)而非 arr[0],可從後往前解碼:arr[i] = arr[i+1] XOR encoded[i]。此變體展示 XOR 解碼的對稱性,可用於驗證:正向解碼的結果若從後往前再解一次應回到原始 first。
延伸思考
- 若
encoded[i] = arr[i] + arr[i+1](加法而非 XOR),給定arr[0],能否同樣逐步還原?此時數值溢位問題如何處理? - XOR 的自反性(
a XOR a = 0)在密碼學的「一次性密碼本(One-Time Pad)」中如何應用?本題的解碼過程與 OTP 的解密有何相似之處? - 若
encoded陣列本身也被加密(例如每個元素再 XOR 一個固定的密鑰k),在不知道k的情況下,能否還原arr?需要哪些額外條件?