[LeetCode] 421. 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 = [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 。

思路

我这里提供一个位运算的做法，大部分内容参考了这个帖子。首先复习一下异或运算规则：两个二进制的数字，同一个位置上的数字不同，XOR 为 1；数字相同的时候，XOR 为 0。所以这里如果要找 XOR 最大的结果，最好能找到两个数字，他们的二进制表达最好在每一位上都不同。而且 XOR 是具有交换律的，如果你有 a ^ b = c，你同时可以得到 a ^ c = b 和 b ^ c = a。假如 a 和 b 是来自于 nums 的数字的话，我们为了要使 c 最大，我们可以试图去找一个前缀很大的数字 a 和一个前缀很小的数字 b，这样他们做 XOR 运算的时候才有可能使 c 的前缀更大。

这里我们创建一个mask去判断每个二进制数字的前缀。mask是由10000…000到11111…111（32位）。随着mask的变大，比如从10000到11111（我这里暂时用5位表示），如果nums里面的数字跟mask比较的时候，他们的前缀里面也包含1的话，在做AND运算的时候，会得到这些前缀。此时我们在找前缀的同时，把这些前缀存到一个hashset里。每一个mask都会与input数组里面的每一个数字做AND运算，得到一个前缀，set里最终留下的是所有unique的前缀。

此时再创建一个mask叫做temp，也是从1 - 31逐渐增加1的个数。这里我理解temp就是在猜最后XOR的结果，然后往回套，看hashset是否存在两个数字a和b满足a ^ b = temp。判断的方式是对于hashset里面的某个元素a，如果满足a ^ temp = b，同时b也在hashset中，则表明找到了一个有效的temp。

复杂度

时间O(n)
空间O(n)

代码

Java实现

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 = 31; i >= 0; i--) {
			// 注意点1：注意保留前缀的方法，mask 是这样得来的
			// 用异或也是可以的 mask = mask ^ (1 << i);
			mask = mask | (1 << i);
			// System.out.println("mask is " + 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);
			System.out.println("temp is " + Integer.toBinaryString(temp));
			for (Integer prefix : set) {
				if (set.contains(prefix ^ temp)) {
					res = temp;
					break;
				}
			}
		}
		return res;
	}
}

二刷我再提供一个前缀树的做法，我参考了这个帖子。难得官方写了一篇好帖子。

对于一个数字，我们可以用一个长度为 32 的二进制数字来表达。如果我们从高位到低位把每个位置上的 digit 放入一棵字典树（这里其实只有 0 和 1 两种情况所以是二叉树），那么对于某个数字 x 而言，如果我要找和他做 XOR 操作结果更大的数字，那么我只要尽量去找每一个 digit 上都与 x 不同的数字即可，这个概念平移到这棵二叉树里，就是在每个 node 上，如果 x 在这个位置上是 1，那么我就尽量去往 0 的那个分支上走，反之如果 x 在这个位置上是 0，那么我就尽量去往 1 的那个分支上走。

具体到这道题，对于某个数字 nums[i]，我会先把前 i - 1 个数字的二进制表达都放到字典树里，那么我在遍历当前这个数字 nums[i] 的时候，我就可以找到与他做 XOR 运算能得到的最大结果是多少。

时间O(nlogc) - n 个数字，每个数字被插入字典树的复杂度为O(logc)
空间O(nlogc)
Java实现

class Solution {
	class Node {
		Node left = null;
		Node right = null;
	}

	Node root = new Node();
	static final int HIGH_BIT = 30;

	public int findMaximumXOR(int[] nums) {
		int n = nums.length;
		int x = 0;
		for (int i = 1; i < n; i++) {
			add(nums[i - 1]);
			x = Math.max(x, check(nums[i]));
		}
		return x;
	}

	public void add(int num) {
		Node cur = root;
		for (int i = HIGH_BIT; i >= 0; i--) {
			int bit = (num >> i) & 1;
			if (bit == 0) {
				if (cur.left == null) {
					cur.left = new Node();
				}
				cur = cur.left;
			} else {
				if (cur.right == null) {
					cur.right = new Node();
				}
				cur = cur.right;
			}
		}
	}

	public int check(int num) {
		Node cur = root;
		int x = 0;
		for (int i = HIGH_BIT; i >= 0; i--) {
			int bit = (num >> i) & 1;
			// 如果当前位是0，我们则应该去找1
			// 反之也是一样，这样XOR的结果才会更大
			// 如果当前是0，应该往右子树走
			// 但如果右子树为空，则只能往左子树走
			if (bit == 0) {
				if (cur.right != null) {
					cur = cur.right;
					x = x * 2 + 1;
				} else {
					cur = cur.left;
					x = x * 2;
				}
			} else {
				if (cur.left != null) {
					cur = cur.left;
					x = x * 2 + 1;
				} else {
					cur = cur.right;
					x = x * 2;
				}
			}
		}
		return x;
	}
}