🌕🌕🌗 421. 数组中两个数的最大异或值

难度: 🌕🌕🌗

问题描述

---

解法

class Solution {
    public int findMaximumXOR(int[] nums) {
        // 思路：
        // 构造字典树，只有左右两个节点，分别表示 0 & 1
        // 1. 遍历元素，初始化字典树
        // 2. 定位到首节点，该节点处 cur.left != null && cur.right != null 正好出现 0 & 1 
        // 3. 递归找到最大运算结果
        Node root = new Node(0);
        // 1. 复杂度 O(30 * N)
        for(int i: nums) {
            // 2^31 - 1 最高位的 1 所在位置为 1 <<< 30
            int monitor = (1 << 30); // 初始参照值与之异或判断该位是否为 1
            Node tmp = root;
            while(monitor > 0) {
                // 根据每位的值进行左右节点的插入
                int cur = (monitor & i);
                if(cur == 0) {
                    if(tmp.left == null) {
                        tmp.left = new Node(0);
                    }
                    tmp = tmp.left;
                } else {
                    if(tmp.right == null) {
                        tmp.right = new Node(1);
                    }
                    tmp = tmp.right;
                }
                monitor >>>= 1;
            }
        }
        // 2. 复杂度 O(31)
        Node node = root;
        int pow = 30;
        // node != null 为了防止只有一条分叉线导致 node == null
        while(node != null && (node.left == null || node.right == null)) {
            if(node.left == null) {
                node = node.right;
            } else {
                node = node.left;
            }
            pow --;
        }
        if(node == null) {
            return 0;
        }
        // node.left != null && node.right != null
        // 出现同时存在 0 & 1 的节点
        return mySol(node.left, node.right, pow);
    }

    private int mySol(Node a, Node b, int pow) {
        // 递归终止条件
        if(a == null || b == null) {
            return 0;
        }
        int res = 0;
        // 求 节点 a & 节点 b 的异或值 
        if(a.val != b.val) {
            // 该位贡献了一份异或值
            res += (1 << pow);
        }
        // 判断往哪个方向递归
        // 每个节点有 2 种分支选择，但若是节点只有一个子节点，那么只剩下一条路
        if(a.left == null) {
            // a.right != null --> a 只能走 right 方向，最理想的情况是 b 能走 left 方向
            // 判断 b 走哪个方向
            if(b.left != null) {
                return res + mySol(a.right, b.left, pow - 1);
            } else {
                return res + mySol(a.right, b.right, pow - 1);
            }
        } else if(a.right == null) {
            // a.left != null
            if(b.right != null) {
                return res + mySol(a.left, b.right, pow - 1);
            } else {
                return res + mySol(a.left, b.left, pow - 1);
            }
        } else {
            // a.left != null && a.right != null
            // 不论走 b 的左边还是右边，总能有一种选择满足同时出现 1 & 0 的情况
            return res + Math.max(mySol(a.left, b.right, pow - 1), mySol(a.right, b.left, pow - 1));
        }
    }
}

class Node {
    int val;
    Node left;
    Node right;
    public Node(int val) {
        this.val = val;
    }
}

---

输出