leetcode
leetcode 1551 ~ 1600
与数组中元素的最大异或值

与数组中元素的最大异或值

难度:

标签:

题目描述

代码结果

运行时间: 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树中插入元素时不会重复插入相同的元素?是否有特定的机制来处理这个问题,还是假设数组中没有重复的元素?
在题解中并没有特别处理数组中可能出现的重复元素,Trie树的结构本身就支持重复插入,因为即使多次插入相同的值,也只会加强Trie树中相应路径的存在性,而不会对最终的XOR查询结果产生影响。因此,可以认为Trie树处理重复元素是无害的。但是,如果业务逻辑需要避免重复计算,可以在插入前通过集合或其他结构预处理以去除重复元素。
🦆
在查询过程中,如果nums的所有元素都大于mi,返回-1的逻辑是如何实现的?具体是依据哪个条件判断的?
该逻辑是通过检查在处理每个查询时Trie树中是否有元素被插入来实现的。具体实现中,使用一个索引`idx`跟踪当前已处理的`nums`元素。如果在处理某个查询(xi, mi)时,`idx`还未增加(即`idx == 0`),这意味着没有任何元素被插入到Trie树中,因为所有的nums元素都大于mi。在这种情况下,直接为该查询返回-1。
🦆
为什么要在处理查询之前对nums进行排序?这样做的具体好处是什么?
对nums进行排序的主要好处是便于高效地处理查询。在查询处理过程中,我们需要将小于等于mi的nums元素插入Trie树。如果nums是排序的,我们可以使用一个单调递增的指针来遍历nums,并停止在第一个大于mi的元素处。这种方法避免了对每个查询重复检查整个nums数组,从而提高了整体效率。
🦆
Trie树的getMaxXor函数在实现中如何确保找到与xi进行XOR操作的最大值?具体的比较和选择逻辑是什么样的?
getMaxXor函数通过贪心算法确保找到最大的XOR结果。对于每一个二进制位,从最高位开始,函数尝试选择能够使得XOR结果最大化的路径。具体地,如果当前位xi为0,优先选择Trie树中的1(如果存在);如果xi为1,则优先选择0(如果存在)。这样的选择是因为XOR操作中不同的位会产生1,从而增大结果。如果在某个位上没有可选择的路径来最大化结果,则选择可用的其他路径。通过这种方式,函数在每一位上都尽可能选取最优值,以确保最终的XOR结果是最大的。

相关问题