[LeetCode] 421. Maximum XOR of Two Numbers in an Array #421

grandyang · 2019-05-30T16:20:57Z

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.

这道题是一道典型的位操作 Bit Manipulation 的题目，我开始以为异或值最大的两个数一定包括数组的最大值，但是 OJ 给了另一个例子 {10,23,20,18,28}，这个数组的异或最大值是 10 和 20 异或，得到 30。那么只能另辟蹊径，正确的做法是按位遍历，题目中给定了数字的返回不会超过 2^31，那么最多只能有 32 位，我们用一个从左往右的 mask，用来提取数字的前缀，然后将其都存入 HashSet 中，我们用一个变量t，用来验证当前位为1再或上之前结果 res，看结果和 HashSet 中的前缀异或之后在不在 HashSet 中，这里用到了一个性质，若 a^b=c，那么 a=b^c，因为t是我们要验证的当前最大值，所以我们遍历 HashSet 中的数时，和t异或后的结果仍在 HashSet 中，说明两个前缀可以异或出t的值，所以我们更新 res 为t，继续遍历，如果上述讲解不容易理解，那么建议自己带个例子一步一步试试，并把每次循环中 HashSet 中所有的数字都打印出来，基本应该就能理解了，算了，还是博主带着大家来看题目中给的例子吧：

3 10 5 25 2 8

11 1010 101 11001 10 1000

我们观察这些数字最大的为 25，其二进制最高位在 i=4 时为1，那么我们的循环 [31, 5] 之间是取不到任何数字的，所以不会对结果 res 有任何影响。

当 i=4 时，我们此时 mask 为前 28 位为 ‘1’ 的二进制数，跟除 25 以外的任何数相‘与’，都会得到0。然后跟 25 的二进制数 10101 相‘与’，得到二进制数 10000，存入 HashSet 中，那么此时 HashSet 中就有0和16两个数字。此时我们的t为结果 res（此时为0）‘或’上二进制数 10000，得到二进制数 10000。然后我们遍历 HashSet，由于 HashSet 是无序的，所以我们会取出0和 16 中的其中一个，如果 prefix 取出的是0，那么 t=16 ‘异或’上0，还等于 16，而 16 是在 HashSet 中存在的，所以此时结果 res 更新为 16，然后 break 掉遍历 HashSet 的循环。实际上 prefix 先取 16 的话也一样，那么 t=16 ‘异或’上 16，等于0，而0是在 HashSet 中存在的，所以此时结果 res 更新为 16，然后 break 掉遍历 HashSet 的循环。

3 10 5 25 2 8

11 1010 101 11001 10 1000

当 i=3 时，我们此时 mask 为前 29 位为 ‘1’ 的二进制数，如上所示，跟数字 3，5，2 中任何一个相‘与’，都会得到0。然后跟 10 的二进制数 1010，或跟8的二进制数 1000 相‘与’，都会得到二进制数 1000，即8。跟 25 的二进制数 11001 相‘与’，会得到二进数 11000，即 24，存入 HashSet 中，那么此时 HashSet 中就有 0，8，和 24 三个数字。此时我们的t为结果 res（此时为 16）‘或’上二进制数 1000，得到二进制数 11000，即 24。此时遍历 HashSet 中的数，当 prefix 取出0，那么 t=24 ‘异或’上0，还等于 24，而 24 是在 HashSet 中存在的，所以此时结果 res 更新为 24，然后 break 掉遍历 HashSet 的循环。大家可以尝试其他的数，当 prefix 取出 24，其实也可以更新结果 res 为 24 的。但是8就不行啦，因为 HashSet 中没有 16。不过无所谓了，我们只要有一个能更新结果 res 就可以了。

3 10 5 25 2 8

11 1010 101 11001 10 1000

当 i=2 时，我们此时 mask 为前 30 位为 ‘1’ 的二进制数，如上所示，跟3的二进制数 11 相‘与’，会得到二进制数0，即0。然后跟 10 的二进制数 1010 相‘与’，会得到二进制数 1000，即8。然后跟5的二进制数 101 相‘与’，会得到二进制数 100，即4。然后跟 25 的二进制数 11001 相‘与’，会得到二进制数 11000，即 24。跟数字2和8相‘与’，分别会得到0和8，跟前面重复了。所以最终 HashSet 中就有0，4，8，和 24 这四个数字。此时我们的t为结果 res（此时为 24）‘或’上二进制数 100，得到二进制数 11100，即 28。那么就要验证结果 res 能否取到28。我们遍历 HashSet，当 prefix 取出0，那么 t=28 ‘异或’上0，还等于 28，但是 HashSet 中没有 28，所以不行。当 prefix 取出4，那么 t=28 ‘异或’上二进制数 100，等于 24，在 HashSet 中存在，Bingo！结果res更新为 28。其他的数可以不用试了。

3 10 5 25 2 8

11 1010 101 11001 10 1000

当 i=1 时，我们此时 mask 为前 31 位为 ‘1’ 的二进制数，如上所示，每个数与 mask 相‘与’后，我们 HashSet 中会有 2，4，8，10，24 这五个数。此时我们的t为结果 res（此时为 28）‘或’上二进制数 10，得到二进制数 11110，即 30。那么就要验证结果 res 能否取到 30。我们遍历 HashSet，当 prefix 取出2，那么 t=30 ‘异或’上2，等于 28，但是 HashSet 中没有 28，所以不行。当 prefix 取出4，那么 t=30 ‘异或’上4，等于 26，但是 HashSet 中没有 26，所以不行。当 prefix 取出8，那么 t=30 ‘异或’上8，等于 22，但是 HashSet 中没有 22，所以不行。当 prefix 取出 10，那么 t=30 ‘异或’上 10，等于 20，但是 HashSet 中没有 20，所以不行。当 prefix 取出 24，那么 t=30 ‘异或’上 24，等于6，但是 HashSet 中没有6，所以不行。遍历完了 HashSet 所有的数，结果 res 没有被更新，还是 28。

3 10 5 25 2 8

11 1010 101 11001 10 1000

当 i=0 时，我们此时 mask 为前 32 位为 ‘1’ 的二进制数，如上所示，每个数与 mask 相‘与’后，我们 HashSet 中会有 2，3，5，8，10，25 这六个数。此时我们的t为结果 res（此时为 28）‘或’上二进制数1，得到二进制数 11101，即 29。那么就要验证结果 res 能否取到 29。取出 HashSet 中每一个数字来验证，跟上面的验证方法相同，这里博主偷懒就不写了，最终可以发现，结果 res 无法被更新，还是 28，所以最终的结果就是 28。

综上所述，我们来分析一下这道题的核心。我们希望用二进制来拼出结果的数，最终结果 28 的二进制数为 11100，里面有三个 ‘1’，我们来找一下都是谁贡献了这三个 ‘1’？在 i=4 时，数字 25 贡献了最高位的 ‘1’，在 i=3 时，数字 25 贡献了次高位的 ‘1’，在 i=2 时，数字5贡献了第三位的 ‘1’。而一旦某个数贡献了 ‘1’，那么之后在需要贡献 ‘1’ 的时候，此数就可以再继续贡献 ‘1’。而一旦有两个数贡献了 ‘1’ 后，那么之后的 ‘1’ 就基本上只跟这两个数有关了，其他数字有 ‘1’ 也贡献不出来。验证方法里使用了前面提到的性质，a ^ b = t，如果t是所求结果话，我们可以先假定一个t，然后验证，如果 a ^ t = b 成立，说明该t可以通过a和b‘异或’得到。参见代码如下：

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int res = 0, mask = 0;
        for (int i = 31; i >= 0; --i) {
            mask |= (1 << i);
            unordered_set<int> s;
            for (int num : nums) {
                s.insert(num & mask);
            }
            int t = res | (1 << i);
            for (int prefix : s) {
                if (s.count(t ^ prefix)) {
                    res = t;
                    break;
                }
            }
        }
        return res;
    }
};

Github 同步地址：

#421

参考资料：

https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/

https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/discuss/130427/()-92

https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/discuss/91049/Java-O(n)-solution-using-bit-manipulation-and-HashMap

https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/discuss/91064/C%2B%2B-22-ms-beats-99.5-array-partitioning-similar-to-quick-sort

LeetCode All in One 题目讲解汇总(持续更新中...)

The text was updated successfully, but these errors were encountered: