【LeetCode】每日一题 2023_11_4 数组中两个数的最大异或值

文章目录

• 刷题前唠嗑
• 题目：数组中两个数的最大异或值
• 结语

刷题前唠嗑

LeetCode? 启动！！！

题目：数组中两个数的最大异或值

题目链接：421. 数组中两个数的最大异或值

题目描述

代码与解题思路

func findMaximumXOR(nums []int) (ans int) {
    for i := 0; i < len(nums); i++ {
        for j := i+1; j < len(nums); j++ {
            ans = max(ans, nums[i]^nums[j])
        }
    }
    return ans
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

一眼顶真，鉴定为暴力出奇迹，暴力？启动！

暴力启动失败。。。（不应该啊，绝对是 LeetCode 更新了样例，10 的 5 次方的复杂度应该是可以暴力过的）

没关系，我其实还有一个思路，就是他想要最大值，我们可以找二进制最高位是能取到 1 的值，然后次高位，以此类推，就能找到最大的异或值。想的很好，但是我不知道咋写，没办法，偷看大佬题解去了

看了少说半个小时的题解，终于有点眉目了，算法菜鸟落泪了

func findMaximumXOR(nums []int) (ans int) {
    mask := 0
    for i := 30; i >= 0; i-- { // 从最高位开始判断
        mp := map[int]bool{} 
        mask |= 1 << i // 把第 i 位, 置为 1
        checkAns := ans | 1 << i // 将 checkAns的 第 i 位, 置为 1
        for _, v := range nums { // 遍历 nums 数组
            v &= mask // i 位之后全置为 0
            if mp[checkAns^v] { // 如果存在两个数异或等于 checkAns 
                ans = checkAns // checkAns 成真，更新 ans
                break
            }
            mp[v] = true // 将 v 塞进 map
        }
    }
    return ans
}

虽然打了很多注释，但不够清楚，我来整体捋一下这道题的思路：

1. 从最高位开始判断（这个很好理解，毕竟是求最大）
2. 理解 checkAns 变量：每次遍历，我们会将 ans 的第 i 位设置成 1，也就是理想中的最大值，接下来的逻辑就是看看 nums 数组中的数进行异或操作能不能得到 i 位为 1 的 checkAns，如果能，就更新 ans，如果不能就继续遍历
3. 理解 mask 变量：mask 将第 i 位之后的值都置为 0，只关注第 i 位及以前的值（具体来说就是这个操作：v &= mask），当 nums 数组中出现一个 v，能让 v^checkAns = map 中的任意一个 v，就证明数组中的两个值异或能得出 checkAns，所以就能更新 ans 的大小了
4. 理解为什么使用 map：使用 map 之后，原本是 O(N) 的匹配，就优化成了 O(1) 的匹配效率，这就是为什么时间复杂度下降的原因

最后补充一下位运算的一个小知识：
a ^ b = c
b ^ b = 0
可得：a = c ^ b

带入题目中：
v ^ (map 中的任意一个 v) = checkAns
v ^ v = 0
(map 中的任意一个 v) = v ^ checkAns

结语

我燃尽了。。。