題目描述:給定一個整數陣列 nums,回傳陣列中任意兩個元素做 XOR 運算所能得到的最大值。
解題思路:暴力法需要 O(n²) 時間逐對計算,但可以利用二進位 Trie 達到 O(32n) = O(n)。
Trie 建立:將每個整數從最高位(第 31 位)到最低位(第 0 位)插入 Trie。Trie 的每個節點有兩個子節點:children[0] 和 children[1],分別代表目前位元為 0 或 1。
最大 XOR 查詢:對每個數 num,在 Trie 中尋找能使 XOR 最大的配對數。從最高位開始,對 num 當前位元值 bit,優先嘗試走向 1 - bit 方向(因為 XOR 需要兩位不同才能得到 1)。若該方向存在,則此位元貢獻 1;否則被迫走相同方向,此位元貢獻 0。逐位累積,得到與 num 配對的最大 XOR 值。
對所有 num 做查詢,取最大值即為答案。
時間複雜度:O(32 × n) = O(n) — 插入與查詢各需遍歷所有 n 個數,每次操作深度為 32 層。
空間複雜度:O(32 × n) = O(n) — Trie 最多有 32n 個節點(每個數插入時最多建立 32 個新節點)。
Struct TrieNode:
children[0], children[1] = null
Function insert(root, num):
node = root
For i from 31 down to 0:
bit = (num >> i) AND 1
If node.children[bit] is null: create new node
Move node to node.children[bit]
Function query(root, num):
node = root
maxXor = 0
For i from 31 down to 0:
bit = (num >> i) AND 1
want = 1 - bit
If node.children[want] exists:
maxXor OR= (1 << i)
Move node to node.children[want]
Else:
Move node to node.children[bit]
Return maxXor
Function findMaximumXOR(nums):
Build Trie by inserting all nums
result = 0
For each num in nums:
result = max(result, query(root, num))
Return result雜湊集合貪心法 O(32n):從最高位逐步構建答案 prefix。對每個位元,假設該位可以為 1(設 candidate = prefix | (1 << i)),遍歷所有數的前 (32-i) 位前綴,存入集合,再對每個前綴 p 檢查 p ^ candidate 是否在集合中。若存在,確認此位為 1。時間複雜度相同,但不需要建立 Trie 結構,程式碼更簡短。
暴力法 O(n²):雙層迴圈對所有 (i, j) 對計算 nums[i] ^ nums[j],取最大值。實作最簡單,但當 n = 2 × 10⁴ 時需要 4 × 10⁸ 次操作,會超時。
線性基(Linear Basis):將所有數插入線性基(Gaussian elimination on GF(2)),然後從線性基中貪心選取使 XOR 最大的組合。此方法更通用,可以解決「k 個數 XOR 最大值」問題,但對本題(k=2)而言,Trie 或雜湊法更直觀。
new 的開銷?i == j),答案是否總為 0?為什麼不是?