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

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你一个由非负整数组成的数组 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⁵
queries[i].length == 2
0 <= nums[j], xi, mi <= 10⁹

# 思路

字典树+贪心+离线

# 解法

class Solution {
    public int[] maximizeXor(int[] nums, int[][] queries) {
        root = new Trie01Node();
        int[] ret = new int[queries.length];
        Integer[] indexMap = new Integer[queries.length];
        for (int i = 0; i < indexMap.length; i++) indexMap[i] = i;
        Arrays.sort(indexMap, Comparator.comparingInt(o -> queries[o][1]));
        Arrays.sort(queries, Comparator.comparingInt(o -> o[1]));
        Arrays.sort(nums);
        int numIndex = 0;
        for (int i = 0; i < queries.length; i++) {
            while (numIndex < nums.length && nums[numIndex] <= queries[i][1]) {
                insert(nums[numIndex]);
                numIndex++;
            }
            //树中的所有数都小于mi
            int v = getV(queries[i][0]);
            ret[indexMap[i]] = v == -1 ? -1 : queries[i][0] ^ v;
        }
        return ret;
    }


    private Trie01Node root;

//    100001011001

    public void insert(int num) {
        int index;
        Trie01Node node = root;
        for (int i = 31; i >= 0; i--) {
            index = ((1 << i) & num) == 0 ? 0 : 1;
            if (node.nexts[index] == null) node.nexts[index] = new Trie01Node();
            node = node.nexts[index];
        }
    }

    //不能找大于limit的值
    public int getV(int num) {
        Trie01Node node = root;
        int tv = 0;
        int index;
        for (int i = 31; i >= 0; i--) {
            if (node == null) return -1;
            index = ((1 << i) & num) == 0 ? 0 : 1;
            if (index == 0) { //期望获得为1的值
                if (node.nexts[1] != null) {
                    node = node.nexts[1];
                    tv = tv * 2 + 1;
                } else {
                    node = node.nexts[0];
                    tv *= 2;
                }
                //新的
            } else {  //期望获得为0的值
                if (node.nexts[0] != null) {
                    node = node.nexts[0];
                    tv *= 2;
                } else {
                    node = node.nexts[1];
                    tv = tv * 2 + 1;
                }
            }
        }
        return tv;
    }

}

class Trie01Node {
    public Trie01Node[] nexts;

    public Trie01Node() {
        nexts = new Trie01Node[2];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

# 总结

分析出几种情况，然后分别对各个情况实现

#Java