leetcode
leetcode 2951 ~ 3000
数组中两个数的最大异或值

数组中两个数的最大异或值

难度:

标签:

题目描述

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)

代码细节讲解

🦆
为什么在构建最大异或结果时,从最高位到最低位逐位尝试,而不是从最低位到最高位或者随机位顺序尝试?
在构建最大异或结果时,从最高位到最低位逐位尝试的原因是异或运算中较高位的差异对最终结果的影响更大。例如,位于更高位置的1(如1000)比位于较低位置的1(如1)对结果的影响更大。因此,首先确保较高位的最大化可以帮助我们尽可能地获得更大的最终异或值。从最高位开始,可以在每一步中尽量保证获得当前可能的最大值,这种贪心策略保证了算法的效率和结果的优化。
🦆
解题中提到的`掩码mask`的具体作用是什么,它是如何帮助确定正在考虑的位?
在题解中,`掩码mask`的作用主要是用于限制和选择整数中的特定位,以便进行异或计算。mask的构建是通过逐位将其设为1(从最高位开始),这样通过与mask的按位与运算(num & mask),可以有效地屏蔽掉整数中位于mask中为0的位置的所有位。这样,我们只保留了从最高位到当前正在考虑的位的信息,其他更低的位则被设为0,从而帮助我们集中考虑和处理每一位的贡献,确保在构建过程中可以逐步确定每一位的最优值。
🦆
在题解算法中,如何保证每次循环中`want`值的选择是最优的?
在算法中,`want`值的选择是基于当前已经获得的最大异或值`ans`来进行的。在每个循环中,通过设定`want`为`ans`再尝试将当前正在考虑的位设置为1(即ans | (1 << i)),这样的设置是希望在保持已有的高位最大异或结果的同时,进一步增加当前位的值。通过检查`want`与已有的数的异或结果是否存在于集合`seen`中,可以验证是否能够实现当前的`want`值。这种方法是贪心算法的体现,每一步都尽量保证在当前可操作的位级上达到最大值,从而整体上实现全局最大异或值。

相关问题