大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
本篇内容介绍了“如何实现数组中两个数的最大异或值”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!
为凤凰等地区用户提供了全套网页设计制作服务,及凤凰网站建设行业解决方案。主营业务为做网站、成都做网站、凤凰网站设计,以传统方式定制建设网站,并提供域名空间备案等一条龙服务,秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求,就会得到认可,从而选择与我们长期合作。这样,我们也可以走得更远!
给你一个整数数组 nums ,返回 nums[i] XOR nums[j] 的最大运算结果,其中 0 ≤ i ≤ j < n 。
进阶:你可以在 O(n) 的时间解决这个问题吗?
提示:
1 <= nums.length <= 2 * 104
0 <= nums[i] <= 231 - 1
链接:https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array
示例 1:
输入:nums = [3,10,5,25,2,8] 输出:28 解释:最大运算结果是 5 XOR 25 = 28.
示例 2:
输入:nums = [0] 输出:0
XOR : 异或运算,1^1=0, 0^0=0, 1^0=1, 0^1=1
// 普通 : O(n^2) 双重循环,解决 class Solution { public int findMaximumXOR(int[] nums) { if(nums == null || nums.length <=1){ return 0; } int len = nums.length; int res = 0; int n = 0; for(int i=0;ires){ res = n; } } } return res; } }
// 进阶 :O(n) : 字典树+贪心 class Tire{ // 树节点,左节点为0,右节点为1 Tire left = null; // 0 Tire right = null; // 1 } class Solution { static Tire root = new Tire(); static final int TIRE_HIGHT = 30; // 树的深度,2^31 - 1,个人认为是31,当30就能满足条件 public int findMaximumXOR(int[] nums) { root = new Tire(); // Leetcode中全局变量的问题,需要自己初始化 if(nums == null || nums.length <=1){ return 0; } int len = nums.length; int res = 0; for(int num:nums) { add(num); res = Math.max(res, check(num)); } return res; } // 生成树,关键:bit =(num>>i)&1,从高位开始构建树,高位越高,ROX才越大。 public static void add(int num) { Tire node = root; for (int i = TIRE_HIGHT; i >= 0; i--) { int bit = (num >> i)&1; if (bit == 0) { if(node.left == null) { node.left = new Tire(); } node = node.left; }else { if (node.right == null) { node.right = new Tire(); } node = node.right; } } } // 贪心算法计算ROX,num某位是1,则找0;反之,找1. public static int check(int num) { Tire node = root; int x = 0; for (int i = TIRE_HIGHT; i >= 0; i--) { int bit = (num >> i)&1; if (bit==0) { if (node.right != null) { node = node.right; x = (x << 1) + 1; }else { node = node.left; x = (x << 1); } }else { if(node.left != null) { node = node.left; x = (x << 1) + 1; }else { node = node.right; x = (x << 1); } } } return x; } }
总结:在数组中找异或值,通过0,1构建树。最大异或值:从高位开始找,通过贪心的思想该位置的异或值等于1最优。
“如何实现数组中两个数的最大异或值”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站,小编将为大家输出更多高质量的实用文章!