与数组中元素的最大异或值
难度:
标签:
题目描述
代码结果
运行时间: 2613 ms, 内存: 162.6 MB
/*
* 思路:
* 1. 对每个查询,过滤出nums中小于等于mi的所有元素。
* 2. 计算这些元素与xi的按位异或值,并找到最大值。
* 3. 如果没有符合条件的元素,则返回-1。
*/
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
public class Solution {
public int[] maximizeXor(int[] nums, int[][] queries) {
Arrays.sort(nums); // 先排序nums数组
return Arrays.stream(queries).mapToInt(query -> {
int xi = query[0];
int mi = query[1];
return Arrays.stream(nums)
.filter(num -> num <= mi)
.map(num -> num ^ xi)
.max()
.orElse(-1);
}).toArray();
}
}
解释
方法:
本题解的核心是使用字典树(Trie)针对整数进行位操作的优化存储。首先,将数组nums排序并对查询数组queries按m值排序以方便处理。对于每个查询(xi, mi),我们将nums中所有不大于mi的元素插入到Trie中。之后,我们使用Trie树的getMaxXor函数来找到与xi进行XOR操作可以获得的最大值。如果没有任何元素被插入到Trie中(即所有nums元素均大于mi),则返回-1。
时间复杂度:
O((n + q) * L)
空间复杂度:
O(nL)
代码细节讲解
🦆
如何确保在Trie树中插入元素时不会重复插入相同的元素?是否有特定的机制来处理这个问题,还是假设数组中没有重复的元素?
▷🦆
在查询过程中,如果nums的所有元素都大于mi,返回-1的逻辑是如何实现的?具体是依据哪个条件判断的?
▷🦆
为什么要在处理查询之前对nums进行排序?这样做的具体好处是什么?
▷🦆
Trie树的getMaxXor函数在实现中如何确保找到与xi进行XOR操作的最大值?具体的比较和选择逻辑是什么样的?
▷