Hard

题目描述

给你一个由非负整数组成的数组 nums。另有一个查询数组 queries，其中 queries[i] = [xi, mi]。

第 i 个查询的答案是 xi 和任何 nums 中不超过 mi 的元素按位异或（XOR）得到的最大值。换句话说，答案是 max(nums[j] XOR xi)，其中所有 j 都满足 nums[j] <= mi。如果 nums 中的所有元素都大于 mi，最终答案就是 -1。

返回一个整数数组 answer 作为查询的答案，其中 answer.length == queries.length 且 answer[i] 是第 i 次查询的答案。

示例 1：

输入：nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
输出：[3,3,7]
解释：
1) 0 和 1 是仅有的两个不超过 1 的整数。0 XOR 3 = 3 而 1 XOR 3 = 2 。二者中的更大值是 3 。
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.

示例 2：

输入：nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
输出：[15,-1,5]

提示：

  • 1 <= nums.length, queries.length <= 10^5
  • queries[i].length == 2
  • 0 <= nums[j], xi, mi <= 10^9

解题思路

这道题要求我们对每个查询找到数组中不超过 mi 的元素与 xi 异或的最大值。

核心思路：

  1. 字典树（Trie）优化异或查询：要最大化异或值，我们需要从最高位开始，尽量让每一位都不同。字典树可以帮助我们快速找到与目标数异或值最大的数。

  2. 离线处理：将查询按照 mi 从小到大排序，将 nums 也排序。这样我们可以维护一个字典树，逐步加入满足条件的数字。

  3. 具体实现：

    • 构建二进制字典树，每个节点存储0和1两个分支
    • 对于每个查询，在字典树中贪心地选择与 xi 当前位不同的路径
    • 使用排序+双指针技巧，确保字典树中只包含 <= mi 的元素

算法步骤：

  1. 将查询和索引绑定后按 mi 排序
  2. 将 nums 排序
  3. 对于每个查询，将所有 <= mi 的数加入字典树
  4. 在字典树中查询与 xi 异或的最大值

代码实现

class Solution {
private:
    struct TrieNode {
        TrieNode* children[2];
        TrieNode() {
            children[0] = children[1] = nullptr;
        }
    };
    
    TrieNode* root;
    
    void insert(int num) {
        TrieNode* node = root;
        for (int i = 30; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (!node->children[bit]) {
                node->children[bit] = new TrieNode();
            }
            node = node->children[bit];
        }
    }
    
    int query(int num) {
        TrieNode* node = root;
        int maxXor = 0;
        for (int i = 30; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int toggledBit = 1 - bit;
            if (node->children[toggledBit]) {
                maxXor |= (1 << i);
                node = node->children[toggledBit];
            } else {
                node = node->children[bit];
            }
        }
        return maxXor;
    }
    
public:
    vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
        root = new TrieNode();
        sort(nums.begin(), nums.end());
        
        vector<pair<pair<int, int>, int>> sortedQueries;
        for (int i = 0; i < queries.size(); i++) {
            sortedQueries.push_back({{queries[i][1], queries[i][0]}, i});
        }
        sort(sortedQueries.begin(), sortedQueries.end());
        
        vector<int> answer(queries.size());
        int idx = 0;
        
        for (auto& q : sortedQueries) {
            int mi = q.first.first;
            int xi = q.first.second;
            int queryIdx = q.second;
            
            while (idx < nums.size() && nums[idx] <= mi) {
                insert(nums[idx]);
                idx++;
            }
            
            if (idx == 0) {
                answer[queryIdx] = -1;
            } else {
                answer[queryIdx] = query(xi);
            }
        }
        
        return answer;
    }
};

class Solution:
    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        class TrieNode:
            def __init__(self):
                self.children = {}
        
        def insert(root, num):
            node = root
            for i in range(30, -1, -1):
                bit = (num >> i) & 1
                if bit not in node.children:
                    node.children[bit] = TrieNode()
                node = node.children[bit]
        
        def query(root, num):
            node = root
            max_xor = 0
            for i in range(30, -1, -1):
                bit = (num >> i) & 1
                toggled_bit = 1 - bit
                if toggled_bit in node.children:
                    max_xor |= (1 << i)
                    node = node.children[toggled_bit]
                else:
                    node = node.children[bit]
            return max_xor
        
        root = TrieNode()
        nums.sort()
        
        # Sort queries by mi along with original indices
        sorted_queries = sorted((mi, xi, i) for i, (xi, mi) in enumerate(queries))
        
        answer = [0] * len(queries)
        idx = 0
        
        for mi, xi, query_idx in sorted_queries:
            # Insert all numbers <= mi into trie
            while idx < len(nums) and nums[idx] <= mi:
                insert(root, nums[idx])
                idx += 1
            
            if idx == 0:
                answer[query_idx] = -1
            else:
                answer[query_idx] = query(root, xi)
        
        return answer

public class Solution {
    public class TrieNode {
        public TrieNode[] Children = new TrieNode[2];
    }
    
    private TrieNode root;
    
    private void Insert(int num) {
        TrieNode node = root;
        for (int i = 30; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (node.Children[bit] == null) {
                node.Children[bit] = new TrieNode();
            }
            node = node.Children[bit];
        }
    }
    
    private int Query(int num) {
        TrieNode node = root;
        int maxXor = 0;
        for (int i = 30; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int toggledBit = 1 - bit;
            if (node.Children[toggledBit] != null) {
                maxXor |= (1 << i);
                node = node.Children[toggledBit];
            } else {
                node = node.Children[bit];
            }
        }
        return maxXor;
    }
    
    public int[] MaximizeXor(int[] nums, int[][] queries) {
        root = new TrieNode();
        Array.Sort(nums);
        
        var sortedQueries = new List<(int mi, int xi, int idx)>();
        for (int i = 0; i < queries.Length; i++) {
            sortedQueries.Add((queries[i][1], queries[i][0], i));
        }
        sortedQueries.Sort((a, b) => a.mi.CompareTo(b.mi));
        
        int[] answer = new int[queries.Length];
        int idx = 0;
        
        foreach (var (mi, xi, queryIdx) in sortedQueries) {
            while (idx < nums.Length && nums[idx] <= mi) {
                Insert(nums[idx]);
                idx++;
            }
            
            if (idx == 0) {
                answer[queryIdx] = -1;
            } else {
                answer[queryIdx] = Query(xi);
            }
        }
        
        return answer;
    }
}

var maximizeXor = function(nums, queries) {
    class TrieNode {
        constructor() {
            this.children = {};
            this.minVal = Infinity;
        }
    }
    
    class Trie {
        constructor() {
            this.root = new TrieNode();
        }
        
        insert(num) {
            let node = this.root;
            node.minVal = Math.min(node.minVal, num);
            
            for (let i = 30; i >= 0; i--) {
                const bit = (num >> i) & 1;
                if (!node.children[bit]) {
                    node.children[bit] = new TrieNode();
                }
                node = node.children[bit];
                node.minVal = Math.min(node.minVal, num);
            }
        }
        
        findMaxXor(num, maxVal) {
            let node = this.root;
            if (node.minVal > maxVal) return -1;
            
            let result = 0;
            for (let i = 30; i >= 0; i--) {
                const bit = (num >> i) & 1;
                const oppositeBit = 1 - bit;
                
                if (node.children[oppositeBit] && node.children[oppositeBit].minVal <= maxVal) {
                    result |= (1 << i);
                    node = node.children[oppositeBit];
                } else {
                    node = node.children[bit];
                }
            }
            return result;
        }
    }
    
    const trie = new Trie();
    for (const num of nums) {
        trie.insert(num);
    }
    
    const result = [];
    for (const [x, m] of queries) {
        result.push(trie.findMaxXor(x, m));
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O((n + q) × 30 + n log n + q log q)，其中 n 是 nums 长度，q 是查询数量。排序需要 O(n log n + q log q)，字典树操作每次最多 30 位
空间复杂度O(n × 30)，字典树最多存储 n 个数字，每个数字最多 30 位

相关题目