[1707] 与数组中元素的最大异或值

[1707] 与数组中元素的最大异或值

力扣原题链接

给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ，其中 queries[i] = [x<sub>i</sub>, m<sub>i</sub>] 。

第 i 个查询的答案是 x<sub>i</sub> 和任何 nums 数组中不超过 m<sub>i</sub> 的元素按位异或（XOR）得到的最大值。换句话说，答案是 max(nums[j] XOR x<sub>i</sub>) ，其中所有 j 均满足 nums[j] <= m<sub>i</sub> 。如果 nums 中的所有元素都大于 m<sub>i</sub>，最终答案就是 -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<sup>5</sup>
• queries[i].length == 2
• 0 <= nums[j], x<sub>i</sub>, m<sub>i</sub><span> </span><= 10<sup>9</sup>

我的思路

这种解法只能通过59的案例，第60个案例超时间了。

根据异或性质中，两个数异或的值不会超过两个数相加的值，可以先排序数组，通过二分查找找到第一个大于该数的值，从该值往下找，直到两数之和低于目前最大的异或值中止。

力扣题解使用二进制懒得看。
力扣题解链接

我的代码

class Solution {
public:
    //二分查找找到第一个大于num的值
    int findHelper(vector<int> &nums,int num)
    {
        int left = 0;
        int right = (int)nums.size() - 1;
        while(left < right)
        {
            int tmp = (right - left) / 2 + left;
            if(nums[tmp] >= num)
            {
                right = tmp;
            }
            else
            {
                left = tmp + 1;
            }
        }
        return left;
    }

    vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
        //std::sort(nums.begin(),nums.end());
        set<int>s(nums.begin(), nums.end());
        nums.assign(s.begin(), s.end());        //利用set排序并去重，减少时间复杂度

        int size = (int)queries.size();

        vector<int> resurt(size,-1);
        for(int i = 0; i < size; ++i)
        {
            int max_num = -1;
            int find_indxe = findHelper(nums,queries[i][1]);
            for(int j = find_indxe; j >= 0; --j)
            {
                if(nums[j] > queries[i][1]) continue;   //不符合的数值
                if(nums[j] + queries[i][0] <= max_num) break; //两数之和无法大于目前最大异或值 中止

                max_num = std::max(nums[j] ^ queries[i][0],max_num);
            }
            resurt[i] = max_num;
        }

        return resurt;
    }
};
​

力扣题解

class Trie {
public:
    const int L = 30;

    Trie* children[2] = {};
    int min = INT_MAX;

    void insert(int val) {
        Trie* node = this;
        node->min = std::min(node->min, val);
        for (int i = L - 1; i >= 0; --i) {
            int bit = (val >> i) & 1;
            if (node->children[bit] == nullptr) {
                node->children[bit] = new Trie();
            }
            node = node->children[bit];
            node->min = std::min(node->min, val);
        }
    }

    int getMaxXorWithLimit(int val, int limit) {
        Trie* node = this;
        if (node->min > limit) {
            return -1;
        }
        int ans = 0;
        for (int i = L - 1; i >= 0; --i) {
            int bit = (val >> i) & 1;
            if (node->children[bit ^ 1] != nullptr && node->children[bit ^ 1]->min <= limit) {
                ans |= 1 << i;
                bit ^= 1;
            }
            node = node->children[bit];
        }
        return ans;
    }
};

class Solution {
public:
    vector<int> maximizeXor(vector<int> &nums, vector<vector<int>> &queries) {
        Trie* t = new Trie();
        for (int val : nums) {
            t->insert(val);
        }
        int numQ = queries.size();
        vector<int> ans(numQ);
        for (int i = 0; i < numQ; ++i) {
            ans[i] = t->getMaxXorWithLimit(queries[i][0], queries[i][1]);
        }
        return ans;
    }
};
​