力扣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,说明这位异或得1
        p = son[p][!u];
      }
      else {
        res = res * 2;//在当前节点不存在!u,说明这位异或得0
        p = 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一定包含最大答案。

相关文章
|
1天前
|
C++ Python
二刷力扣--数组
二刷力扣--数组
|
2天前
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
|
2天前
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
|
2天前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
|
2天前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
2天前
|
算法
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
|
6天前
|
存储 算法 数据可视化
深入解读力扣154题:寻找旋转排序数组中的最小值 II(多种方法及详细ASCII图解)
深入解读力扣154题:寻找旋转排序数组中的最小值 II(多种方法及详细ASCII图解)
|
6天前
|
存储 算法 数据可视化
|
6天前
|
存储 传感器 算法
LeetCode题目89:格雷码 递归、迭代及位操作在数组合并中的应用
LeetCode题目89:格雷码 递归、迭代及位操作在数组合并中的应用
|
6天前
|
存储 算法 数据挖掘
LeetCode 题目 81:搜索旋转排序数组 II
LeetCode 题目 81:搜索旋转排序数组 II