数组中两个数的最大异或值
难度:
标签:
题目描述
English description is not available for the problem. Please switch to Chinese.
代码结果
运行时间: 54 ms, 内存: 30.3 MB
/*
题目思路:
1. 使用 Stream API 对数组进行处理。
2. 由于 Stream API 并不适合这种复杂的数据结构问题,我们将用基本的 Stream 操作来进行部分的转换。
3. 此解法主要还是借助基本的 Java 数据结构和操作。
*/
import java.util.Arrays;
public class Solution {
public int findMaximumXOR(int[] nums) {
int max = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
max = Math.max(max, nums[i] ^ nums[j]);
}
}
return max;
}
}
解释
方法:
这个题解使用了一种基于贪心和位操作的方法。首先,题解试图逐步构建结果的每一位,从最高位到最低位,每一步都尽可能使结果的该位为1。具体操作是,先用一个掩码mask来确定当前正在考虑的位,然后尝试构建一个期望的最大值want。接着,使用一个集合seen存储当前所有数字经过掩码处理后的结果。对于每个数,检查want与该数的XOR结果是否已经在seen中,如果存在,则表明可以将当前want作为新的最大异或结果。这个过程从最高位开始,依次向下,每个位置都尽力使异或结果的当前位为1,从而得到全局最大的异或结果。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在构建最大异或结果时,从最高位到最低位逐位尝试,而不是从最低位到最高位或者随机位顺序尝试?
▷🦆
解题中提到的`掩码mask`的具体作用是什么,它是如何帮助确定正在考虑的位?
▷🦆
在题解算法中,如何保证每次循环中`want`值的选择是最优的?
▷