421. 数组中两个数的最大异或值(前缀树(Trie))

题目来源:421. 数组中两个数的最大异或值 给你一个整数数组 nums ,返回 nums[i] XOR nums[j] 的最大运算结果,其中 0 ≤ i ≤ j < n 。 进阶:你可以在 O(n) 的时间解决这个问题吗? 题解:   x=ai​⊕aj 等价于 aj​=x⊕ai,设计一种「从高位到低位依次确定 x 二进制表示的每一位」的方法,其精髓在于   1)如果x满足aj​=x⊕ai,那么其高位部分也满足aj​=x⊕ai。   2)由于我们需要找出最大的 x,因此在枚举每一位时,我们先判断 x 的这一位是否能取到 1。​​
  方法一:哈希表
  1. 如何判断 x 的k位是否能取到 1,我们先将数组前k+1位保存到集合seen中。
  2. 假设x 包含从最高位开始到第 k+1 个二进制位为止的部分,则前k位为 xNext = x*2+1。   3. 枚举nums,查询集合seen中是否存在 xNext ^(num>>i)。
var findMaximumXOR = function(nums) {
    const HIGH_BIT = 30;
    let x = 0;
    for(let i=HIGH_BIT;i>=0;i--){
        let seen = new Set();
        for(let num of nums){
            seen.add(num>>i);
        }

        let xNext = 2*x+1;
        let found = false;
        for(let num of nums){
            if(seen.has(xNext^(num>>i))){
                found = true;
                break;
            }
        }
        if(found){
            x = xNext;
        }else{
            x = xNext - 1;
        }
    }
    return x;
}
let nums  = [3,10,5,25,2,8]
console.log(nums, findMaximumXOR(nums));

nums  =  [0]
console.log(nums, findMaximumXOR(nums));
nums  =  [2,4]
console.log(nums, findMaximumXOR(nums));
nums  = [8,10,2]
console.log(nums, findMaximumXOR(nums));

nums  = [14,70,53,83,49,91,36,80,92,51,66,70]
console.log(nums, findMaximumXOR(nums));

方法二: Trie树,左子树为0, 右子树为1

var findMaximumXOR = function(nums) {
    //因为0 <= nums[i] <= 231 - 1,所以可以通过获取最大数的二进制位数缩小Trie树层数。
    const HIGH_BIT = Math.max(...nums).toString(2).length;
    let n = nums.length;

    class bitTrie {
        constructor(){
            this.root = this.Trie();   
        }
        Trie(){
            let obj = new Object();
            obj.left = null;
            obj.right = null;
            return obj;
        }
        add(num){
            let cur = this.root;
            for(let i=HIGH_BIT;i>=0;i--){
                let bit = (num>>i)&1;
                if(bit === 0){
                    if(!cur.left){
                        cur.left = this.Trie();
                    }
                    cur = cur.left;
                }else{
                    if(!cur.right){
                        cur.right = this.Trie();
                    }
                    cur = cur.right;
                }
            }
        }
        check(num){
            let cur = this.root;
            let x = 0;
            for(let i = HIGH_BIT;i>=0;i--){
                let bit = (num>>i)&1;
                if(bit === 0){
                    if(cur.right){
                        cur = cur.right;
                        x=2*x+1;
                    }else{
                        cur = cur.left;
                        x=2*x;
                    }
                }else{
                    if(cur.left){
                        cur = cur.left;
                        x=2*x+1;
                    }else{
                        cur = cur.right;
                        x=2*x;
                    }
                }
            }
            return x;
        }
    }

    let root = new bitTrie();
    let x = 0;
    for(let i = 1;i<n;i++){
        root.add(nums[i-1]);
        x = Math.max(x, root.check(nums[i]));
    }

    return x;
}

提示:

1 <= nums.length <= 2 * 104 0 <= nums[i] <= 231 - 1
上一篇:前缀树(java实现)


下一篇:字典树(前缀树)