2935. 找出强数对的最大异或值 II(2349)

给你一个下标从 0 开始的整数数组 nums 。如果一对整数 x 和 y 满足以下条件，则称其为 强数对 ：

  • |x - y| <= min(x, y)

你需要从 nums 中选出两个整数，且满足：这两个整数可以形成一个强数对，并且它们的按位异或（XOR）值是在该数组所有强数对中的 最大值 。

返回数组 nums 所有可能的强数对中的 最大 异或值。

注意，你可以选择同一个整数两次来形成一个强数对。

示例 1：

1
2
3
4
输入：nums = [1,2,3,4,5]
输出：7
解释：数组 nums 中有 11 个强数对：(1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5) 和 (5, 5) 。
这些强数对中的最大异或值是 3 XOR 4 = 7 。

示例 2：

1
2
3
4
输入：nums = [10,100]
输出：0
解释：数组 nums 中有 2 个强数对：(10, 10) 和 (100, 100) 。
这些强数对中的最大异或值是 10 XOR 10 = 0 ，数对 (100, 100) 的异或值也是 100 XOR 100 = 0 。

示例 3：

1
2
3
4
输入：nums = [500,520,2500,3000]
输出：1020
解释：数组 nums 中有 6 个强数对：(500, 500), (500, 520), (520, 520), (2500, 2500), (2500, 3000) 和 (3000, 3000) 。
这些强数对中的最大异或值是 500 XOR 520 = 1020 ；另一个异或值非零的数对是 (5, 6) ，其异或值是 2500 XOR 3000 = 636 。

提示：

  • 1 <= nums.length <= 5 * 10^4
  • 1 <= nums[i] <= 2^20 - 1

0-1树

用cnt记录当前节点的数量，来判断节点是否已经被删除（cnt为0则说明被remove）

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
class Trie {
    class TrieNode {
        int cnt;  // 需要维护数量
        TrieNode[] children = new TrieNode[2];
    }
    TrieNode root = new TrieNode();
    void insert(int word) {
        TrieNode cur = root;
        for (int i = 30; i >= 0; i--) {
            int index = word >> i & 1;
            if (cur.children[index] == null) {
                cur.children[index] = new TrieNode();
            }
            cur = cur.children[index];
            cur.cnt++;
        }
    }
    void remove(int word) {
        TrieNode cur = root;
        for (int i = 30; i >= 0; i--) {
            int index = word >> i & 1;
            cur = cur.children[index];
            cur.cnt--;
        }
    }
    int search(int word) {
        TrieNode cur = root;
        int res = 0;
        for (int i = 30; i >= 0; i--) {
            int index = word >> i & 1;
            if (cur.children[index ^ 1] == null || cur.children[index ^ 1].cnt == 0) {
                cur = cur.children[index];
            }
            else {
                res |= 1 << i;
                cur = cur.children[index ^ 1];
            }
        }
        return res;
    }
}
class Solution {
    public int maximumStrongPairXor(int[] nums) {
        // | x - y | <= min(x, y)
        // 这种有绝对值的式子一定要化简！！！！！！
        // 设 x < y, 则 y <= 2*x（排序后就可以满足x < y的条件）
        int n = nums.length, res = 0, left = 0;
        Arrays.sort(nums);
        Trie tree = new Trie();
        for (int y : nums) {
            tree.insert(y);
            int x = nums[left];
            while (y > 2*x) {
                tree.remove(x);
                left++;
                x = nums[left];
            }
            res = Math.max(res, tree.search(y));
        }
        return res;
    }
}