专栏首页眯眯眼猫头鹰的小树杈leetcode421. Maximum XOR of Two Numbers in an Array

leetcode421. Maximum XOR of Two Numbers in an Array

题目要求

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai< 231.

Find the maximum result of ai XOR aj, where 0 ≤_i_,_j_<_n_.

Could you do this in O(_n_) runtime?

Example:

Input: [3, 10, 5, 25, 2, 8]

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.

现有一个非空的整数数组,问如何能够找出整数数组中两个整数的异或结果的最大值。

思路一:贪婪算法

这里解释一下高分答案贪婪算法的思路。每一次我们都试图假设第i位的异或结果为1,并且判断是否能够从数组中找到任意两个整数,其在该位上的异或值为1。如果找不到,则说明任意两个整数在该位的异或结果只能是0。接着对第i-1位进行同样的判断。从高位开始的原因在于,从贪婪角度的算法看来,我们更希望高位为1,其生成的异或值更大。

代码如下:

    public int findMaximumXOR(int[] nums) {
        //32位到第i位为止算出的异或最大值
        int maxResult = 0;
        int mask = 0;
        for(int i = 31 ; i>=0 ; i--) {
            //i~32位全为1
            mask |= (1 << i);
            Set<Integer> set = new HashSet<>();
            //取所有整数的前32-i位的结果并保存
            for(int num : nums) {
                set.add(num | mask);
            }
            
            //假设第i位能够异或出结果1
            int greedyTry = maxResult | (1 << i);
            //使用结论a^b=c,则a^c=b。根据该结论,我们假设整数数组中的两个整数在第i为的值为1,且set中存储了所有的a的值,异或出b的值后看b是否也在set中。
            for(int num : set) {
                if(set.contains(greedyTry ^ num)) {
                    maxResult = greedyTry;
                    break;
                }
            }
        }
        return maxResult;

    }

思路二:Trie

假如我们用Trie的数据结构将所有的整数以32位平铺开,一个Trie节点表示第i位是否有为0或是为1的数字:则每个Trie节点有三种可能:

  1. Trie节点无子节点:则表明该节点为叶节点,无需继续处理
  2. Trie节点有一个子节点:表明只有一个数字在该位上的值为0或1
  3. Trie节点有两个子节点:表明该位上有0也有1

代码如下:

    public int findMaximumXOR2(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }
        //将所有整数存入Trie结构
        TrieNode root = new TrieNode(-1);
        for (int i = 0; i < nums.length; i += 1) {
            addToTrie(root, nums[i]);
        }
        return findMaximum(root, 31);
    }
    
    private int findMaximum(TrieNode node, int pos) {
        if (pos == 0) {
            return 0;
        }
        
        //表明在第pos位上只有1,异或结果一定为0
        if (node.zero == null) {
            return findMaximum(node.one, pos - 1);
        }
        //表明在第pos上只有0,异或结果一定为0
        if (node.one == null) {
            return findMaximum(node.zero, pos - 1);
        }
        return findMaximum(node.zero, node.one, pos - 1);
    }
    
    private int findMaximum(TrieNode node1, TrieNode node2, int pos) {
        //计算第pos上的异或结果
        int result = (node1.val ^ node2.val) << pos;
        //pos==0代表为叶节点
        if (pos == 0) {
            return result;
        }
        //获取node1的可用子节点和node2的可用子节点
        TrieNode next1 = null;
        TrieNode next2 = null;
        if (node1.zero != null && node1.one == null) {
            next1 = node1.zero;
        } else if (node1.zero == null && node1.one != null) {
            next1 = node1.one;
        }
        if (node2.zero != null && node2.one == null) {
            next2 = node2.zero;
        } else if (node2.zero == null && node2.one != null) {
            next2 = node2.one;
        }
        //满足node1和node2均只有一个子节点,将二者进行迭代比较
        if (next1 != null && next2 != null) {
            return result + findMaximum(next1, next2, pos - 1);
        }
        //node1不为空代表node1只有一个可用子节点,如果子节点为0,则选node2的one子节点,否则选node2的zero子节点
        if (next1 != null) {
            if (next1.val == 0) {
                next2 = node2.one;
            } else {
                next2 = node2.zero;
            }
            return result + findMaximum(next1, next2, pos - 1);
        }
        //同上
        if (next2 != null) {
            if (next2.val == 0) {
                next1 = node1.one;
            } else {
                next1 = node1.zero;
            }
            return result + findMaximum(next1, next2, pos - 1);
        }
        //node1和node2均有两个子节点,则将node1.one和node2.zero 与 node1.zero和node2.one进行比较得出最大异或值
        return result + Math.max(findMaximum(node1.zero, node2.one, pos - 1), findMaximum(node1.one, node2.zero, pos - 1));
    }
    
    private void addToTrie(TrieNode root, int x) {
        TrieNode curr = root;
        int[] binary = toBinary(x);
        for (int i = 0; i < binary.length; i += 1) {
            if (binary[i] == 0) {
                if (curr.zero == null) {
                    curr.zero = new TrieNode(0);
                }
                curr = curr.zero;
            } else {
                if (curr.one == null) {
                    curr.one = new TrieNode(1);
                }
                curr = curr.one;
            }
        }
    }
    
    private int[] toBinary(int x) {
        int[] result = new int[31];
        for (int i = 30; i >= 0; i -= 1) {
            result[i] = x & 1;
            x >>= 1;
        }
        return result;
    }
    
    static class TrieNode {
        int val;
        TrieNode zero;
        TrieNode one;
        
        public TrieNode(int val) {
            this.val = val;
            zero = null;
            one = null;
        }
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode542. 01 Matrix

    Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each ...

    眯眯眼的猫头鹰
  • leetcode430. Flatten a Multilevel Doubly Linked List

    从深度优先遍历的角度来看,每次遇到一个包含子节点中间双链表节点,就递归的调用展开方法将其展开,并将展开的结果插入到当前节点的后面。这里需要注意双链表前节点前后指...

    眯眯眼的猫头鹰
  • 395. Longest Substring with At Least K Repeating Characters

    这是一个经典的分治法解决的问题,关键在于我们如何将这个问题分解为更小的子问题。反过来想,这个子字符串一定不包含什么元素呢?当一个元素出现的总次数小于k,那么该元...

    眯眯眼的猫头鹰
  • 分享用于学习C++图像处理的代码示例

    为了便于学习图像处理并研究图像算法, 俺写了一个适合初学者学习的小小框架。 麻雀虽小五脏俱全。 采用Decoder:stb_image https://gith...

    cpuimage
  • 《Kotlin 反应式编程》使用 RxKotlin 实现一个极简的 http DSL ( Reactive Programming Using Rx Kotlin )《Kotlin 反应式编程》使用

    我们现在已经基本知道 Kotlin 中 DSL 的样子了。但是这些 DSL 都是怎样实现的呢?本节我们就通过实现一个极简的http DSL来学习创建 DSL 背...

    一个会写诗的程序员
  • 合唱团

    题目:有 n 个学生站成一排,每个学生有一个能力值,从这 n 个学生中按照顺序选取 k 名学生,要求相邻两个学生的位置编号的差不超过 d,使得这 k 个学生的能...

    Meet相识
  • Django实战-信息资讯-切片加载与搜索

    Django网络应用开发的5项基础核心技术包括模型(Model)的设计,URL 的设计与配置,View(视图)的编写,Template(模板)的设计和Form(...

    小团子
  • 关于版权行业的现状你知道多少?又有多少是你不知道的?

    小墨第一次对版权这个东西有认知的时候,大概是在学生时代的高中阶段,那时候语文老师要求每个同学都必备一本《中国汉语词典》,第一次听闻这部词汇巨作的小墨不大能理解这...

    墨者安全科技
  • Python学习笔记:单例模式

    单例模式:一个类无论实例化多少次,返回的都是同一个实例,例如:a1=A(), a2=A(), a3=A(),a1、a2和a3其实都是同一个对象,即print(a...

    py3study
  • 聊聊sentinel的NettyHttpCommandCenter

    com/alibaba/csp/sentinel/transport/command/NettyHttpCommandCenter.java

    codecraft

扫码关注云+社区

领取腾讯云代金券