【每日一题】数组中两个数的最大异或值-Toy模板网

这篇具有很好参考价值的文章主要介绍了【每日一题】数组中两个数的最大异或值。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Tag

【哈希集合】【位运算-异或和】【数组】【2023-11-04】

题目来源

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

【每日一题】数组中两个数的最大异或值,LeetCode每日一题,哈希集合,位运算-异或,数组,2023-11-04

题目解读

找出数组中两个数的最大异或结果。

解题思路

一看数据量达到了 $10^5$ ，那时间复杂度为 $O(n^2)$ 的方法必定超时，因此需要去找 $O (n l o g n)$ 或者 $O (n)$ 时间复杂度的方法。

对于本题，最直白的想法是枚举数组中的两个数，计算异或值，找出最大值返回即可，但是该方法的需要两次枚举数，属于嵌套循环，时间复杂度为 $O(n^2)$ ，一定超时，故需要考虑其他方法。

接下来将介绍两种方法来解决本题：

哈希集合；
字典树（待完成…）。

方法一：哈希集合

以下思路与代码主要参考【图解】简洁高效，一图秒懂！（Python/Java/C++/Go/JS/Rust）。

为了得到最大的异或和数，简称为 结果，我们希望 结果 的二进制数从高位到低位尽可能出现更多的 1。为什么对二进制数进行判断？因为，位运算都是二进制位之间的运算（异或和、按位与等等），我们对二进制数进行判断会更加接近底层运算（异或和、按位与等等）。

跳出从数组中直接找数的固化思维，根据 结果 的特征，我们从最高位到最低位来找数。最高位也就是数组中最大数的二进制数长度减一，我们从该位开始枚举 i：

当前需要找的结果是 newAns = res | (1 << i)，也就是从数组中找到两个数（低于 i 的比特位为 0）满足这两个数的异或和等于 newAns，如果有，则更新 res = newAns，否则 res 不变；
判断两个数的异或和的解题思想是两数之和哈希表解法。把代码中的减法改成异或就行，这是因为如果 $a\oplus b = newAns$ ，那么两边同时异或 b，由于 $b\oplus b = 0$ ，所以得到 $\oplus b$ 。这样就可以一边枚举 b，一边在哈希表中查找 $newAns \oplus b$ 了。

实现代码

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int mx = *max_element(nums.begin(), nums.end());
        int high_bit = mx ? 31 - __builtin_clz(mx) : -1;

        int res = 0, mask = 0;
        unordered_set<int> seen;
        for (int i = high_bit; i >= 0; --i) {
            seen.clear();
            mask |= (1 << i);
            int new_ans = res | (1 << i);
            for (int x : nums) {
                x &= mask;
                if (seen.contains(new_ans ^ x)) {
                    res = new_ans;
                    break;
                }
                seen.insert(x);
            }
        }
        return res;
    }
};

复杂度分析

时间复杂度： $O (n l o gU)$ ， $n$ 是数组 nums 的长度， $U$ 是数组中最大元素的位数。

空间复杂度： $O (n)$ ，哈希表中至多存放 n 个数。

其他语言

python3

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        ans = mask = 0
        high_bit = max(nums).bit_length() - 1
        for i in range(high_bit, -1, -1):  # 从最高位开始枚举
            mask |= 1 << i
            new_ans = ans | (1 << i)  # 这个比特位可以是 1 吗？
            seen = set()
            for x in nums:
                x &= mask  # 低于 i 的比特位置为 0
                if new_ans ^ x in seen:
                    ans = new_ans  # 这个比特位可以是 1
                    break
                seen.add(x)
        return ans