原文链接: https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array

英文原文

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

 

Example 1:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

Example 2:

Input: nums = [0]
Output: 0

Example 3:

Input: nums = [2,4]
Output: 6

Example 4:

Input: nums = [8,10,2]
Output: 10

Example 5:

Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127

 

Constraints:

• 1 <= nums.length <= 2 * 105
• 0 <= nums[i] <= 231 - 1

中文题目

给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

进阶：你可以在 O(n) 的时间解决这个问题吗？

 

示例 1：

输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.

示例 2：

输入：nums = [0]
输出：0

示例 3：

输入：nums = [2,4]
输出：6

示例 4：

输入：nums = [8,10,2]
输出：10

示例 5：

输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127

 

提示：

• 1 <= nums.length <= 2 * 104
• 0 <= nums[i] <= 231 - 1

通过代码

高赞题解

异或运算的性质

解决这个问题，我们首先需要利用异或运算的一个性质：

如果 a ^ b = c 成立，那么a ^ c = b 与 b ^ c = a 均成立。

即 如果有三个数，满足其中两个数的异或值等于另一个值，那么这三个数的顺序可以任意调换。

（说明：利用这条性质，可以不使用第 3 个变量而交换两个变量的值。）

• 那么如何理解这个性质呢？因为异或运算其实就是 二进制下不进位的加法，你不妨自己举几个例子，在草稿纸上验证一下。

如何应用到本题？

这道题找最大值的思路是这样的：因为两两异或可以得到一个值，在所有的两两异或得到的值中，一定有一个最大值，我们推测这个最大值应该是什么样的？即根据“最大值”的存在性解题（一定存在）。在这里要强调一下：

我们只用关心这个最大的异或值需要满足什么性质，进而推出这个最大值是什么，而不必关心这个异或值是由哪两个数得来的。

（上面这句话很重要，如果读者一开始看不明白下面的思考，不妨多看几遍我上面写的这句话。）

于是有如下思考：

1、二进制下，我们希望一个数尽可能大，即希望越高位上越能够出现“1”，这样这个数就是所求的最大数，这是贪心算法的思想。

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 位。

(温馨提示：下面的幻灯片中，有几页上有较多的文字，可能需要您停留一下，可以点击右下角的后退 “|◀” 或者前进 “▶|” 按钮控制幻灯片的播放。)

<,,,,,>

参考代码 1：

题目说数组的最大数小于 2 的 31 次方，所以二进制应该是 31 位，那么最外层的 for 循环只需要执行 31 次。

这里感谢 @coder233 指出原本代码中的问题。

[]
import java.util.HashSet;
import java.util.Set;

public class Solution {

    // 先确定高位，再确定低位（有点贪心算法的意思），才能保证这道题的最大性质
    // 一位接着一位去确定这个数位的大小
    // 利用性质： a ^ b = c ，则 a ^ c = b，且 b ^ c = a

    public int findMaximumXOR(int[] nums) {
        int res = 0;
        int mask = 0;
        for (int i = 30; i >= 0; i--) {
            // 注意点1：注意保留前缀的方法，mask 是这样得来的
            // 用异或也是可以的 mask = mask ^ (1 << i);
            mask = mask | (1 << i);

            // System.out.println(Integer.toBinaryString(mask));
            Set<Integer> 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 (set.contains(prefix ^ temp)) {
                    res = temp;
                    break;
                }
            }
        }
        return res;
    }
}

[]
class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        res = 0
        mask = 0
        for i in range(30, -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

复杂度分析：

• 时间复杂度：$O(N)$，把整个数组看了 $31$ 次，即 $O(31N) = O(N)$。
• 空间复杂度：$O(n)$，这里的 $n$ 是哈希表的长度，具体长度是多少，与输入的规模、扩容策略、负载因子和冲突策略等有关。例如 Java 在 JDK 1.8 以后，当哈希值冲突的时候，先把冲突的元素放在单链表上，当冲突的键值大于 8 的时候，再转成红黑树。
  参考资料：《jdk8中HashMap的优化和底层内存的优化》。

统计信息

通过次数	提交次数	AC比率
34274	55111	62.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言