力扣421. 数组中两个数的最大异或值（字典树）

本文主要是介绍力扣421. 数组中两个数的最大异或值（字典树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

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

思路：

题目意思呢非常清晰，就是求一个数组中任意两个数的最大异或值。很明显，直接暴力两重for循环时间复杂度太高了。我们可以把数组中的每一个数字都看出一个31位的二进制序列，根据异或的特性，二进制位不同的数异或得1，也就是说，我们要想找到的异或对最大，那么我们就尽量让这两个数得二进制位都不一样，并且优先从高位考虑。

这里我们可以用字典树来存放数组中每一个数的二进制序列，对于每一个节点都有两个儿子节点，0或者1，假如在这个树里要找一个与x异或最大的数，我们先找与x二进制中最高位的数异或得1的数，换句话说就是找不一样的数呗，假如x的最高位是1，那么要想异或的答案最大，我们看看这个树里面有没有这个位上是0的数，如果有走到这个节点去继续找下一位。

用一个二维数组son[p][u]来模拟一个字典树，第一维表示字典树的节点，第二维表示每个节点的子节点。son[p][u]的值表示这个节点的儿子节点的编号。

代码：

#define _CRT_SECURE_NO_WARNINGS 1
const int N = 1e5 + 10, M = 31 * N;//每个元素都有31位二进制序列
int son[M][2], idx;class Solution {
public:void insert(int x) {int p = 0;for (int i = 30; i >= 0; i--) {int u = x >> i & 1;if (!son[p][u])son[p][u] = ++idx;//更新节点编号p = son[p][u];//找到儿子节点的编号}}long long query(int x) {long long res = 0;int p = 0;for (int i = 30; i >= 0; i--) {int u = x >> i & 1;if (son[p][!u]) {res = res * 2 + 1;//在当前节点存在！u,说明这位异或得1p = son[p][!u];}else {res = res * 2;//在当前节点不存在！u,说明这位异或得0p = son[p][u];}}return res;}int findMaximumXOR(vector<int>& nums) {memset(son, 0, sizeof(son));idx = 0;int ans = 0;for (auto it : nums) {insert(it);int res = query(it);ans = max(ans, res);}return  ans;}
};

注意

为什么是一边插入一边查询呢？

根据异或规则，a^b=c等价于b^a=c，所以，异或对的顺序不会影响答案。我们在插入x的时候，可以在x之前的数中找与x异或最大的值，后面的数插进去后也是同样的操作，这样一来，对于任意一个元素x,它都有机会跟任意一个元素异或，所以得到的ans一定包含最大答案。

这篇关于力扣421. 数组中两个数的最大异或值（字典树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---