leetcode 1707. 与数组中元素的最大异或值

题目

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

解题思路

• 将查询数组queries[i] = [xi, mi]，按照m进行排序，并且记录下原来每个查询所在的位置。
• 将nums数组也进行排序，这样的话，只需要每一个查询维护一个单调递增的指针cur即可，满足nums[cur]<=mi,而nums[0…cur]里面的元素也是小于mi的，因为排序以后的查询数组的mi是递增的，所以每遍历完一个查询queries[i] = [xi, mi]，下一个遍历只需要把cur指针移动至满足num[cur]<=mi+1即可。

字典树

因为nums[j]的取值范围为0 <= nums[j], xi, mi <= 109，所以我们只需要将nums[j]的后30位取出来构造字典树即可，从根节点到叶子节点，代表从高位到低位，Trie[] children=new Trie[2]代表下一位是否可以取0或者1，例如下标0为null的话，证明下一位不能为0。所以找最大的异或结果的话，可以通过从根节点开始，尽量走一些使得当前位异或结果为1的路径，因为根节点到叶子节点是从高位到低位的，所以优先选择使得异或高位为1

代码

class Solution {

    public int[] maximizeXor(int[] nums, int[][] queries) {

        int n=queries.length;
        int[] res = new int[n];
        int[][] nq = new int[n][3];
        Arrays.sort(nums);

        for (int i = 0; i < n; i++) {
            nq[i][0]=queries[i][0];
            nq[i][1]=queries[i][1];
            nq[i][2]=i;
        }
        int cur=0;
        Trie root = new Trie();
        Arrays.sort(nq,(o1, o2) -> o1[1]-o2[1]);
        for (int i = 0; i < n; i++) {
            while (cur<nums.length&&nums[cur]<=nq[i][1])
            {
                root.add(nums[cur]);
                ++cur;
            }
            res[nq[i][2]]=cur==0?-1:root.get(nq[i][0]);
        }
        return res;

    }
}    
public class Trie{
       static final int h=30;
        Trie[] children=new Trie[2];
        void add(int val){
            Trie node=this;
            for (int i=h-1;i>=0;i--){

                int cur=(val>>i)&1;
                if(node.children[cur]==null)
                {
                    node.children[cur]=new Trie();
                }
                node=node.children[cur];
            }
        }
        int get(int val){
            Trie node=this;
            int res=0;
            for (int i=h-1;i>=0;i--){
                int t=(val>>i)&1;
                if(node.children[t^1]!=null){
                    res|=1<<i;
                    t^=1;
                }
                node=node.children[t];

            }
            return res;
        }
    }