数组中两个数的最大异或值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 * 10⁴
0 <= nums[i] <= 2³¹ - 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

# 总结

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