数组中两个数的最大异或值

难度中等

给定一个非空数组，数组中元素为 a0, a1, a2, … , an-1，其中 0 ≤ ai < 2^31

找到 ai 和 aj 最大的异或 (XOR) 运算结果，其中0 ≤ i , j < n 。

你能在O(n)的时间解决这个问题吗？

示例:
输入: [3, 10, 5, 25, 2, 8]
输出: 28
解释: 最大的结果是 5 ^ 25 = 28.

初始思路

暴力法虽然简单，但是。。。都能想到，而且复杂度很高

正确思路

异或就是对应bit位上如果相同，那么两者运算结果为0，不同则为 1，即:

• 1 ^ 1 = 0 ^ 0 = 0
• 0 ^ 1 = 1 ^ 0 = 1

即要想异或出来的数字大，那么应该尽量保持两位是不同的!，这样对应位异或出来为1，结果才会比较大！
那么什么时候最大呢?

尽量使高位异或出 1 才越能保持最大！！！

为什么呢？因为有 1 * * * * 一定大于 0 * * * * ！ 性质

就是不管低位情况如何，只要高位为 1，一定比高位不是 1 的要大， 所以在遍历过程中，只需要寻找与当前位不同的 ，使其异或结果为 1 即可！如若没有则并无影响。

这个过程中，可以使用前缀树来保存每一个数字的各位情况!
尽量寻找高位上不同于当前位的结点则体现贪心

实现方法： 前缀树 + 贪心

package ddx.December.day6;

public class Normal_421 {
    public int maxXOR(int[] nums) {
        BitTrieNode root = buildBitTrie(nums);
        return searchMaXOR(nums,root);
    }
    //前缀树 + 贪心!
    public int searchMaXOR(int[] nums, BitTrieNode root){
        int max = -1; //记录最大值
        for(int num : nums){//遍历数组，找到每个数字与哪个数字异或结果最大!
            BitTrieNode curNode = root;
            for(int index = 31;index >= 0;index--){
                int curBit = num & (1 << index); //拿到数字最高位
                if(curBit == 0){ //如果最高位是0 ，那么我需要前缀树中对应位为 1 的
                    curNode = curNode.one != null ? curNode.one:curNode.zero; //尽量寻找 与当前bit位相反的结点！！！！！
                }else{ //反之亦然
                    curNode = curNode.zero != null ? curNode.zero:curNode.one; //尽量寻找 与当前bit位相反的结点！！！！！
                }
            }
            max = Math.max(max,num ^ curNode.val); //更新最大值！此时curode.val就是与 num异或最大的数字！！！
        }
        return max;
    }

    public BitTrieNode buildBitTrie(int[] nums) { //创建比特位前缀树
        BitTrieNode root = new BitTrieNode(-1); //初始化根节点
        for (int num : nums) {
            BitTrieNode curNode = root;
            for (int index = 31; index >= 0; index--) { //每个数最多不超过32位！将这32位全部创建完
                int curBit = num & (1 << index); //拿到当前位
                if (curBit == 0) {
                    if (curNode.zero == null) { //若没有则创建
                        curNode.zero = new BitTrieNode(0);
                    }
                    curNode = curNode.zero;
                } else {
                    if (curNode.one == null) {//若没有则创建
                        curNode.one = new BitTrieNode(1);
                    }
                    curNode = curNode.one;
                }
            }
            curNode.val = num; //赋值
        }
        return root;
    }

}

class BitTrieNode {
    public BitTrieNode zero;
    public BitTrieNode one;
    public int val;

    BitTrieNode(int val) {
        this.val = val;
    }
}

输出结果

与3异或结果最大的数为：25   异或结果为 :26
与10异或结果最大的数为：25   异或结果为 :19
与5异或结果最大的数为：25   异或结果为 :28
与25异或结果最大的数为：5   异或结果为 :28
与2异或结果最大的数为：25   异或结果为 :27
与8异或结果最大的数为：25   异或结果为 :17

本作品采用《CC 协议》，转载必须注明作者和本文链接