題目敘述 1310. XOR Queries of a Subarray
給定一個整數陣列arr，和一串區間XOR請求queries。
請計算queries所請求的區間XOR值，並且以陣列的形式返回答案。
測試範例
Example 1:Input: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
Output: [2,7,14,8]
Explanation:
The binary representation of the elements in the array are:
1 = 0001
3 = 0011
4 = 0100
8 = 1000
The XOR values for queries are:
[0,1] = 1 xor 3 = 2
[1,2] = 3 xor 4 = 7
[0,3] = 1 xor 3 xor 4 xor 8 = 14
[3,3] = 8
Example 2:
Input: arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
Output: [8,0,4,4]
約束條件
Constraints:
1 <= arr.length, queries.length <= 3 * 10^4
arr陣列 和 queries陣列長度都介於1~三萬之間。
1 <= arr[i] <= 10^9
每個陣列元素都介於1~十億之間。
queries[i].length == 2
每個query標明 起點索引 和 終點索引。
0 <= lefti<= righti< arr.length
0 < 起點 <= 終點 < arr陣列長度
演算法 利用XOR性質 和 前綴和觀念
如果還不熟悉Prefix sum 前綴和的讀者，請參考這篇文章。
➕用Python來實現 Prefix sum 前綴和 | 小松鼠的演算法樂園 (vocus.cc)
XOR運算有一個很好的性質，同樣的變數XOR兩次會成雙成對消去=0。
A XOR A = 0
接著，再借用前綴和的觀念，建立一個prefix XOR table。
arr[0] ⊕ arr[1] ⊕ ... arr[起點-1]
⊕ arr[0] ⊕ arr[1] ⊕ ... arr[起點-1] ⊕ arr[起點] ⊕ ... ⊕ arr[終點]
= arr[起點] ⊕ ... ⊕ arr[終點]
= 題目query所求
程式碼 利用XOR性質 和 前綴和觀念
# XOR property review:
'''
Associativity:
(A XOR B) XOR C = A XOR (B XOR C)
Commutativity:
A XOR B = B XOR A
Idempotency:
A XOR A = 0
'''
class Solution:
def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
result, size = [], len(arr)
look_up_table = [0] * ( size+1 )
# table[i] = arr[0] XOR arr[1] XOR ... XOR arr[i-1]
for i in range(size):
look_up_table[i+1] = look_up_table[i] ^ arr[i]
# compute query, q, by look-up table as well as XOR property
'''
Left = ( prefix leading temrs )
Right = ( prefix leading temrs ) XOR arr[ q[0] ] XOR ... XOR arr[ q[1] ]
Left XOR Right = arr[ q[0] ] XOR ... XOR arr[ q[1] ]
'''
for q in queries:
left = look_up_table[ q[0] ]
right = look_up_table[ q[1] + 1 ]
result.append( left ^ right )
return result
複雜度分析
時間複雜度: O(n + q)
O(n)時間建立prefix XOR table
O(q)計算每一條區間XOR計算請求。
空間複雜度: O(n)
需要O(n)空間來建立prefix XOR table。
