<small id='mVAU'></small> <noframes id='6v94DuRC3'>

  • <tfoot id='2lIkJR'></tfoot>

      <legend id='LZR5Iyja'><style id='c2bRTyu'><dir id='hnJDI087W'><q id='Z9qrj'></q></dir></style></legend>
      <i id='LPpizH'><tr id='GV7zYyW231'><dt id='ZuBvg9d1'><q id='jBZJNO5Y'><span id='jAJk'><b id='zUfClWP'><form id='sHY8AuKLfP'><ins id='Q1C5'></ins><ul id='tGdDU9Biyq'></ul><sub id='bMKrPWlN'></sub></form><legend id='udyYNr'></legend><bdo id='JOmNBF1Vp'><pre id='NKBpMRTD'><center id='O2uZVN5g'></center></pre></bdo></b><th id='MV03e'></th></span></q></dt></tr></i><div id='r8buG'><tfoot id='lmijEJGOup'></tfoot><dl id='1T4eV8EY'><fieldset id='48ICLNSJ'></fieldset></dl></div>

          <bdo id='Y6H1'></bdo><ul id='RILc5zfv2B'></ul>

          1. <li id='YyMKf5XRWJ'></li>
            登陆

            图解 LeetCode 第 421 题:数组中两个数的最大异或值

            admin 2019-12-12 287人围观 ,发现0个评论



            今日共享的标题来源于 LeetCode 第 421 号问题:数组中两个数的最大异或值。在 异或 这个知识点里边归于一个中高难度的标题。

            标题描绘

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

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

            你能在 O(n) 的时刻处理这个问题吗?

            示例:

            输入: [3, 10, 5, 25, 2, 8]
            输出: 28
            解说: 最大的成果是 5 ^ 25 = 28.

            标题解析

            处理这个问题,咱们首要需求运用异或运算的一个性质:

            假如 a ^ b = c 建立,那么a ^ c = b 与 b ^ c = a 均建立。

            假如有三个数,满意其间两个数的异或值等于另一个值,那么这三个数的次序能够恣意互换

            • 那么怎么了解这个性质呢?由于异或运算其实便是二进制下不进位的加法,你无妨自己举几个比如,在草稿纸上验证一下。

            那这个性质怎么应用到本题呢?

            这道题找最大值的思路是这样的:由于两两异或能够得到一个值,在一切的两两异或得到的值中,必定有一个最大值,咱们估测这个最大值应该是什么样的?即根据“最大值”的存在性解题(必定存在)。在这儿要着重一下:

            咱们只用关怀这个最大的异或值需求满意什么性质,从而推出这个最大值是什么,而不用关怀这个异或值是由哪两个数得来的。

            (上面这句话很重要,假如读者一开端看不了解下面的考虑,无妨多看几遍我上面写的这句话。)

            所以有如下考虑:

            1、二进制下,咱们期望一个数尽可能大,即期望越高位上越能够呈现“1”,这样图解 LeetCode 第 421 题:数组中两个数的最大异或值这个数便是所求的最大数,这是贪心算法的思维。

            2、所以,咱们能够从最高位开端,到最低位,首要假定高位是 “1”,把这 n 个数悉数遍历一遍,看看这一位是不是真的能够是“1”,不然这一位就得是“0”,判别的根据是上面“异或运算的性质”,即下面的第 3 点;

            3、假如 a ^ b = max 建立 ,max 表明当时得到的“最大值”,那么必定有 max ^ b = a 建立。咱们能够先假定当时数位上的值为 “1”,再把当时得到的数与这个 n 个数的 前缀(由所以从高位到低位看,所以称为“前缀”)进行异或运算,放在一个哈希表中,再顺次把一切 前缀 与这个假定的“最大值”进行异或今后得到的成果放到哈希表里查询一下,假如查得到,就阐明这个数位上能够是“1”,不然就只能是 0(看起来很晕,能够看代码了解)。

            一种极点的状况是,这 n 个数在某一个数位上悉数是 0 ,那么恣意两个数异或今后都只能是 0,那么假定当时数位是 1 这件工作就不建立。

            4、怎么得到前缀,能够用掩码(mask),掩码能够进行如下结构,将掩码与原数顺次进行“与”运算,就能得到前缀。

            10000000000000000000000000000000
            11000000000000000000000000000000
            11100000000000000000000000000000
            11110000000000000000000000000000
            11111000000000000000000000000000
            11111100000000000000000000000000
            11111110000000000000000000000000
            11111111000000000000000000000000
            11111111100000000000000000000000
            11111111110000000000000000000000
            11111111111000000000000000000000
            11111111111100000000000000000000
            11111111111110000000000000000000
            11111111111111000000000000000000
            11111111111111100000000000000000
            11111111111111110000000000000000
            11111111111111111000000000000000
            11111111111111111100000000000000
            11111111111111111110000000000000
            11111111111111111111000000000000
            11111111111111111111100000000000
            11111111111111111111110000000000
            11111111111111111111111000000000
            11111111111111111111111100000000
            11111111111111111111111110000000
            11111111111111111111111111000000
            11111111111111111111111111100000
            11111111111111111111111111110000
            11111111111111111111111111111000
            11111111111111111111111111111100
            11111111111111111111111111111110
            11111111111111111111111111111111

            以标题中的数组 [3, 10, 5, 25, 2, 8] 为例,下面解说这个最大的两两异或值是怎么得到的,这儿为了便利演示,只展现一个数二进制的低 8 位。

            图片演示

            LeetCode 第 421 题:数组中两个数的最大异或值-1

            LeetCode 第 421 题:数组中两个数的最大异或值-2

            LeetCode 第 421 题:数组中两个数的最大异或值-3

            LeetCode 第 421 题:数组中两个数的最大异或值-4

            LeetCode 第 421 题:数组中两个数的最大异或值-5

            LeetCode 第 421 题:数组中两个数的最大异或值-6

            代码完成

            Python 代码:

            class Solution:
            def findMaximumXOR(self, nums: List[int]) -> int:
            res = 0
            mask = 0
            for i in range(31, -1, -1):
            mask |= (1 << i)
            # 当时得到的一切前缀都放在这个哈希表中
            s = set()
            for num in nums:
            s.add(mask & num)
            # 先“贪心肠”假定这个数位上是 “1” ,假如悉数前缀都看完,都不契合条件,这个数位上便是 “0”
            temp = res | (1 << i)
            for prefix in s:
            if temp ^ prefix in s:
            res = temp
            break
            return res

            Java 代码:

            import java.ut修改器il.HashSet;
            import java.util.Set;
            public class Solution {
            // 先确认高位,再确认低位(有点贪心算法的意思),才干确保这道题的最大性质
            // 一位接着一位去确认这个数位的巨细
            // 运用性质:a ^图解 LeetCode 第 421 题:数组中两个数的最大异或值 b = c ,则 a ^ c = b,且 b ^ c = a
            public int findMaximumXOR(int[] nums) {
            int res = 0;
            int mask = 0;
            for (int i = 31; i >= 0; i--) {
            // 留意点1:留意保存前缀的办法,mask 是这样得来的
            // 用异或也是能够的 mask = mask ^ (1 << i);
            mask = mask | (1 << i);
            // System.out.println(Integer.toBinaryString(mask));
            Set set = new HashSet<>();
            for (int num : nums) {
            // 留意点2:这儿运用 & ,保存前缀的意思(从高位到低位)
            set.add(num & mask);
            }
            // 这儿先假定第 n 位为 1 ,前 n-1 位 res 为之前迭代求得
            int temp = res | (1 << i);
            for (Integer prefix : set) {
            if图解 LeetCode 第 421 题:数组中两个数的最大异或值 (set.contains(prefix ^ temp)) {
            res = temp;
            break;
            }
            }
            }
            return res;
            }
            public static void main(String[] args) {
            int[] nums = {3, 10, 5, 25, 2, 8};
            Solution2 solution2 = new Solution2();
            int maximumXOR = solution2.findMaximumXOR(nums);
            System.out.println(maximumXOR);
            }
            }

            复杂度剖析

            • 时刻复杂度:(),把整个数组看了 32次,即 (32)=()。
            • 空间复杂度:(1),运用了一个哈希表,这个哈希表最多存 32 个前缀,(32)=(1)。


            请关注微信公众号
            微信二维码
            不容错过
            Powered By Z-BlogPHP