数组中两个数的最大异或值Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。
进阶：你可以在 O(n) 的时间解决这个问题吗？
示例 1：
输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.
示例 2：
输入：nums = [0]
输出：0
示例 3：
输入：nums = [2,4]
输出：6
示例 4：
输入：nums = [8,10,2]
输出：10
示例 5：
输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127
提示：
- 1 <= nums.length <= 2 * 104
- 0 <= nums[i] <= 231 - 1
# 思路
// 前缀树节点
private static class Node {
int val = 0;
Node[] next = new Node[2];
}
# 解法
class Solution {
// 前缀树节点
private static class Node {
int val = 0;
Node[] next = new Node[2];
}
public int findMaximumXOR(int[] nums) {
// 寻找最大的数字，确定最长需要几位表示二进制
int max = Integer.MIN_VALUE;
for (int num: nums) max = Math.max(max, num);
int length = Integer.toBinaryString(max).length();
// 插入前缀树
Node head = new Node();
for (int num : nums) {
Node cur = head;
for (int i = length; i >= 0; i--) {
int bit = num >> i & 1;
if (cur.next[bit] == null) {
cur.next[bit] = new Node();
}
cur = cur.next[bit];
}
cur.val = num;
}
max = Integer.MIN_VALUE;
// 一个一个数字的测试，寻找当前数字的最大异或值
for (int num : nums) {
Node cur = head;
for (int i = length; i >= 0; i--) {
int bit = num >> i & 1;
// 能往相反的方向走尽量往相反的方向走
if (cur.next[1 - bit] != null) {
cur = cur.next[1 - bit];
} else {
cur = cur.next[bit];
}
}
// 记录最大值
max = Math.max(max, num ^ cur.val);
}
return max;
}
}
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
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
# 总结
- 分析出几种情况，然后分别对各个情况实现
