【教3妹学编程-算法题】数组中两个数的最大异或值

3妹：“太阳当空照，花儿对我笑，小鸟说早早早，你为什么背上炸药包”
2哥 :3妹，什么事呀这么开心呀。
3妹：2哥你看今天的天气多好啊，阳光明媚、万里无云、秋高气爽，适合秋游。
2哥：是啊，都快立冬了，天气还是这么热。今年的冬天比以往来的要晚一些。
3妹：晚来也是要来的，看天气预报 下周要降温，估计没几天这种暖的天气了。
2哥：注意保暖啊3妹，看你们女生还穿着裙子，不能只要美丽，就冻人啊。
3妹：我才不，天冷了我就穿秋裤，卷死她们。
2哥：说到卷她们，不如做一道题，在技术上卷死她们。 内外兼修~

题目：

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

示例 1：

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

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

提示：

1 <= nums.length <= 2 * 10^5
0 <= nums[i] <= 2^31 - 1

思路：

假设我们已经确定了 x 最高的若干个二进制位，当前正在确定第 k 个二进制位。根据题意，我们希望第 k 个二进制位能够取到 1。
解题思路如代码中注释：

java代码：

class Solution {// 最高位的二进制位编号为 30static final int HIGH_BIT = 30;public int findMaximumXOR(int[] nums) {int x = 0;for (int k = HIGH_BIT; k >= 0; --k) {Set<Integer> seen = new HashSet<Integer>();// 将所有的 pre^k(a_j) 放入哈希表中for (int num : nums) {// 如果只想保留从最高位开始到第 k 个二进制位为止的部分// 只需将其右移 k 位seen.add(num >> k);}// 目前 x 包含从最高位开始到第 k+1 个二进制位为止的部分// 我们将 x 的第 k 个二进制位置为 1，即为 x = x*2+1int xNext = x * 2 + 1;boolean found = false;// 枚举 ifor (int num : nums) {if (seen.contains(xNext ^ (num >> k))) {found = true;break;}}if (found) {x = xNext;} else {// 如果没有找到满足等式的 a_i 和 a_j，那么 x 的第 k 个二进制位只能为 0// 即为 x = x*2x = xNext - 1;}}return x;}
}