題目描述:給定整數陣列 nums 和查詢陣列 queries,每個查詢 queries[i] = [xi, mi],求 xi XOR nums[j] 的最大值,其中 nums[j] <= mi。若不存在滿足條件的 nums[j],回傳 -1。
解題思路(離線排序 + 二進位 Trie):
若對每個查詢獨立建 Trie,時間為 O(n · q),會超時。關鍵觀察:若先按 mi 升序排序查詢,再同步按升序將 nums 中 <= mi 的元素插入 Trie,每個元素只需插入一次。
演算法步驟:
queries 按 mi 升序排序(記錄原始索引);nums 也排序。j 追蹤下一個要插入 Trie 的 nums 元素。(xi, mi):
nums[j] <= mi 的元素到 Trie(j++)。xi 當前位元相反的分支。二進位 Trie 節點只有 children[2](代表 bit 0 或 1),最多 31 層(覆蓋 30 位非負整數)。
時間複雜度:O((n + q) log n + n · 31 + q · 31) — 排序 nums 和 queries 各 O(n log n) 和 O(q log q);每個 nums 元素插入 Trie 一次 O(31);每個查詢在 Trie 中搜尋 O(31);整體為 O((n + q) log(n + q))。
空間複雜度:O(n · 31) — Trie 最多 n × 31 個節點(每個元素 31 位,每位一個節點)。
1. Sort nums ascending.
2. Sort query indices by mi ascending.
3. Initialize Trie with single root node, pointer j = 0.
4. For each query index idx in sorted order:
a. While j < len(nums) and nums[j] <= mi: insert(nums[j]); j++.
b. If j == 0: ans[idx] = -1.
c. Else: ans[idx] = query(xi) // Greedy max XOR in trie.
5. Return ans.
query(num):
For bit from 30 down to 0:
want = 1 - ((num >> bit) & 1)
If trie has child[want]: take it, result |= (1 << bit).
Else: take child[1-want].對每個查詢,線性掃描所有 nums[j] <= mi 的元素,計算 XOR 取最大值。時間 O(n · q),空間 O(1)。當 n = q = 10⁵ 時有 10¹⁰ 次操作,嚴重超時,僅適合驗證小測資。
若查詢必須線上處理,可為每個 mi 值預先建立一個「版本 Trie」(持久化 Trie),查詢時直接用 mi 對應的版本。時間 O((n + q) · 31),空間 O(n · 31)。實作複雜,但支援線上查詢,適合強制線上的場景。
將所有元素和查詢按照最高位分組,遞迴地對每一位決定答案的對應位。本質上是將 Trie 結構展開為遞迴分治,理論等效但實作更複雜,不如顯式 Trie 直觀。
nums[j] >= mi(下界限制),離線策略應如何調整(降序排序)?Trie 的操作有何不同?li <= nums[j] <= mi),能否用持久化 Trie(Persistent Trie)解決?時間複雜度如何?