LeetCode 1707. 与数组中元素的最大异或值（Trie树）

Michael阿明

发布于 2021-09-06 11:05:25

3740

发布于 2021-09-06 11:05:25

文章被收录于专栏：Michael阿明学习之路

文章目录

- 1. 题目
- 2. 解题

1. 题目

给你一个由非负整数组成的数组 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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/maximum-xor-with-an-element-from-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

参考文章：字符串匹配算法（Trie树）

在线处理：节点中添加一个 MIN 字段，记录子树中最小的数，将数字的各个二进制位插入trie树，查找的时候走相反的位的路线（如果存在的话）
离线处理：对数组、查询排序，mi 小的先查询，将数组中满足 mi 的限制的插入 trie 树，其余步骤一样

class trie{ // 在线处理
public:
    trie* next[2] = {NULL,NULL};
    int MIN = INT_MAX;
    void insert(int n){
        trie *cur = this;
        cur->MIN = min(cur->MIN, n);
        for(int i = 31; i >= 0; --i)
        {
            int bit = (n>>i)&1;
            if(!cur->next[bit])
                cur->next[bit] = new trie();
            cur = cur->next[bit];
            cur->MIN = min(cur->MIN, n);
        }
    }
    int getMaxXOR(int n, int limit)
    {
        trie *cur = this;
        if(cur->MIN > limit) return -1;
        int res = 0;
        for(int i = 31; i >= 0; --i)
        {
            int bit = (n>>i)&1;
            if(cur->next[bit^1] && cur->next[bit^1]->MIN <= limit)
            {
                res |= 1<<i;
                bit ^= 1;
            }
            cur = cur->next[bit];
        }
        return res;
    }
};
class Solution {
public:
    vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
        trie *t = new trie();
        for(auto n : nums)
            t->insert(n);
        vector<int> ans(queries.size());
        for(int i = 0; i < queries.size(); ++i)
        {
            int num = queries[i][0], limit = queries[i][1];
            ans[i] = t->getMaxXOR(num, limit);
        }
        return ans;
    }
};

936 ms 261 MB C++

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/05/23 ，如有侵权请联系 cloudcommunity@tencent.com 删除

https