题目描述
leetcode 困难题
给你一个整数数组 nums （下标 从 0 开始 计数）以及两个整数：low 和 high ，请返回 漂亮数对 的数目。
漂亮数对 是一个形如 (i, j) 的数对，其中 0 <= i < j < nums.length 且 low <= (nums[i] XOR nums[j]) <= high 。
示例1：
1
2
3
4
5
6
7
8
9
| 输入：nums = [1,4,2,7], low = 2, high = 6
输出：6
解释：所有漂亮数对 (i, j) 列出如下：
- (0, 1): nums[0] XOR nums[1] = 5
- (0, 2): nums[0] XOR nums[2] = 3
- (0, 3): nums[0] XOR nums[3] = 6
- (1, 2): nums[1] XOR nums[2] = 6
- (1, 3): nums[1] XOR nums[3] = 3
- (2, 3): nums[2] XOR nums[3] = 5
|
提示1：
1
2
3
| 1 <= nums.length <= 2 * 10^4
1 <= nums[i] <= 2 * 10^4
1 <= low <= high <= 2 * 10^4
|
01字典树
题目要求的是异或值在 $[low, high]$ 区间的数对数量，设 $f(x)$ 表示异或值在 $[0, x]$ 区间的数对数量，那么通过容斥原理原问题可以转换成求 $f(high) - f(low - 1)$ 。
“对于数组异或计数问题，我们通常可以使用01字典树来解决”
01字典树的定义类似字典树，不同的是01字典树的子节点只存在 $0$、$1$ 结点两种可能，分别代表二进制位的 $0$、$1$，并按照从高位到低位的顺序存储一个数的二进制，即根节点存储最高位的二进制，且通过一个变量 $cnt$ 存储以当前二进制为前缀的数的个数。
由于数据范围为 $[1, 2 * 10^4]$ ，所以我们只需要存储一个数的 $[0, 14]$ 位二进制即可，因为 $2^{15} - 1 > 2*10^4$ 。
先设 $search(num, x)$ 表示当前树中与 $num$ 的异或值小于等于 $x$ 的数的数量。那么对于 $f(x)$，只需要顺序遍历数组，累加当前元素的 $search(nums[i], x)$ 并将当前元素加入到01字典树中就能得到结果。
对于任意一个数 $x < y$ ，都存在一个数 $k$ ，使得他们的二进制表示中的最高位到 $k + 1$ 位都相同，而第 $k$ 位却为小于的关系。
对于 $search(num, x)$ 的具体实现如下：设结果为 $ret$，我们从根节点开始遍历字典树，设当前遍历到的树节点为 $p$，同时从最高位开始遍历 $num$ 和 $x$ ，设当前遍历到第 $i$ 位，且 $num$ 的第 $i$ 位为 $cur$：
- 如果 $x$ 的第 $i$ 位为 $1$ ，直接将 $p.node[cur].cnt$ 累加到 $ret$ 中，这是因为 $cur \oplus cur = 0$，而 $x$ 的第 $i$ 位又为 $1$，所以 $cur \oplus cur = 0$ 这条路径后的节点不管是什么，显然都小于 $x$ ，也就是说 $i$ 即为上面所说的 $k$；然后再将 $p$ 指向 $p.node[cur \oplus 1]$，这是因为 $cur \oplus (cur \oplus 1) = 1$，即异或值的当前二进制位与 $x$ 相等，尝试搜索在更低位小于 $x$ 的可能，也就是当前 $k$ 为更小的可能。
- 类似的，如果 $x$ 的第 $i$ 位为 $0$ ，那么只需要将 $p$ 指向 $p.node[cur]$ 即可，因为 $cur \oplus cur = 0$ 。
遍历结束后，还需要将 $ret$ 加上 $p.cnt$ ，因为是闭区间，数对的异或值可以等于 $x$ 。
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
| class Solution {
public int countPairs(int[] nums, int low, int high) {
return f(nums, high) - f(nums, low - 1);
}
private int f(int[] nums, int x) {
Trie trie = new Trie();
int ret = 0;
for (int i = 0; i < nums.length; i++) {
ret += trie.search(nums[i], x);
trie.add(nums[i]);
}
return ret;
}
}
class Trie{
Trie[] node = new Trie[2];
int cnt;
public void add(int num){
Trie p = this;
for (int i = 14; i >= 0; i--) {
int cur = (num >> i) & 1;
if (p.node[cur] == null) {
p.node[cur] = new Trie();
}
p.node[cur].cnt++;
p = p.node[cur];
}
}
public int search(int num, int x) {
Trie p = this;
int ret = 0;
for (int i = 14; i >= 0; i--) {
int cur = (num >> i) & 1;
if(((x >> i) & 1) == 1){
if (p.node[cur] != null) {
ret += p.node[cur].cnt;
}
if (p.node[cur ^ 1] == null) {
return ret;
}
p = p.node[cur ^ 1];
} else {
if (p.node[cur] == null) {
return ret;
}
p = p.node[cur];
}
}
return ret + p.cnt;
}
}
|