421. 数组中两个数的最大异或值(中等)

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

题目描述

给你一个整数数组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 * 10^4
0 <= nums[i] <= 2^31 - 1

题目分析

根据题目中的说明，x的个数是有限的，它的值是从0到2^31 – 1，那我可不可以指定x从2^31 - 1递减到0，判断存不存在nums[i] XOR nums[j] = x 。这么做是可以的，而且x不需要从2^31 - 1开始递减，而是从nums中最大一个就可以了，但是这样遍历次数太多了，太暴力了，就不这样做了。

要想获得最大的x，就要从最高位开始看，尽量保证高位为1，那么是不是可以不像上边那样直接指定x的值，而是从高位开始确定x的值，一次确定一位，直到最后得到x的值。

比如我先假设x的最高位为1，那么是不是说只要nums中存在两个数，他们的最高位异或为1就可以了；
如果成立，我再假设x的次高位为1，那么就是nums中存在两个数它们的前两位异或的值为11，如果不存在这样的两个数呢？那就说明x的次高位一定是0，x最前边两位就是10，这里假设不存在这样的两个数，所以x前两位就是10
同样的，假设x第三位是1，判断nums中是否存在两个数前三位异或的值是101，如果存在，就确定x前三位是101，否则就是100
就这样一直判断到最后一位就可以了

public class Solution {

  public int findMaximumXOR(int[] nums) {
    int x = 0;
    //set存放nums中每个元素从第30位到第i位的二进制

    // 每次确定一位
    for (int i = 30; i >= 0; i--) {
      Set<Integer> set = new HashSet<>();
      for (int num : nums) {
        // num是31位，如果右移30得到的就是最高位
        set.add(num >> i);
      }
      x = x << 1;
      // x先左移一位再加一，就是假设x的第i位为1
      int tempX = x + 1;
      for (Integer num : set) {
        if (set.contains(tempX ^ num)) {
          // 如果找到了说明x的第i位是1，把tempX赋给x
          //否则就是x只左移，没有加1，就是x的第i位为0
          x = tempX;
          break;
        }
      }
    }
    return x;
  }

  public static void main(String[] args) {
    int[] nums = {3, 10, 5, 25, 2, 8};
    System.out.println(new Solution().findMaximumXOR(nums));
  }
}

复制代码

总结

代码中要注意的地方

num >> i，表示把num右移i位，num >> 1相当于num / 2，如果一个十进制5，5 / 2 = 5 >> 1 = (101 >> 1)₂ = (10)₂，就是把二进制101右移一位变成10
x << 1，表示x左移一位，二进制101左移一位变成1010
“tempX ^ num，表示异或，相同值异或结果为 0，不同值异或为1`