Tag

【哈希集合】【位運算-異或和】【數(shù)組】【2023-11-04】

題目來源

421. 數(shù)組中兩個數(shù)的最大異或值

題目解讀

找出數(shù)組中兩個數(shù)的最大異或結(jié)果。

解題思路

一看數(shù)據(jù)量達(dá)到了 $10^5$，那時間復(fù)雜度為 $O(n^2)$ 的方法必定超時，因此需要去找 $O(nlogn)$ 或者 $O(n)$ 時間復(fù)雜度的方法。

對于本題，最直白的想法是枚舉數(shù)組中的兩個數(shù)，計算異或值，找出最大值返回即可，但是該方法的需要兩次枚舉數(shù)，屬于嵌套循環(huán)，時間復(fù)雜度為 $O(n^2)$，一定超時，故需要考慮其他方法。

接下來將介紹兩種方法來解決本題：

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

方法一：哈希集合

以下思路與代碼主要參考 【圖解】簡潔高效，一圖秒懂?。≒ython/Java/C++/Go/JS/Rust）。

為了得到最大的異或和數(shù)，簡稱為 結(jié)果，我們希望 結(jié)果 的二進(jìn)制數(shù)從高位到低位盡可能出現(xiàn)更多的 1。為什么對二進(jìn)制數(shù)進(jìn)行判斷？因為，位運算都是二進(jìn)制位之間的運算（異或和、按位與等等），我們對二進(jìn)制數(shù)進(jìn)行判斷會更加接近底層運算（異或和、按位與等等）。

跳出從數(shù)組中直接找數(shù)的固化思維，根據(jù) 結(jié)果 的特征，我們從最高位到最低位來找數(shù)。最高位也就是數(shù)組中最大數(shù)的二進(jìn)制數(shù)長度減一，我們從該位開始枚舉 i：

• 當(dāng)前需要找的結(jié)果是 newAns = res | (1 << i)，也就是從數(shù)組中找到兩個數(shù)（低于 i 的比特位為 0）滿足這兩個數(shù)的異或和等于 newAns，如果有，則更新 res = newAns，否則 res 不變；
• 判斷兩個數(shù)的異或和的解題思想是 兩數(shù)之和 哈希表解法。把代碼中的減法改成異或就行，這是因為如果 $a\oplus b=newAns$，那么兩邊同時異或 b，由于 $b\oplus b=0$，所以得到 $a=newAns\oplus b$。這樣就可以一邊枚舉 b，一邊在哈希表中查找 $newAns\oplus b$ 了。

實現(xiàn)代碼

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;
    }
};

復(fù)雜度分析

時間復(fù)雜度：$O(nlogU)$，$n$ 是數(shù)組 nums 的長度，$U$ 是數(shù)組中最大元素的位數(shù)。

空間復(fù)雜度：$O(n)$，哈希表中至多存放 n 個數(shù)。

其他語言

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

寫在最后

如果文章內(nèi)容有任何錯誤或者您對文章有任何疑問，歡迎私信博主或者在評論區(qū)指出 ??????。

如果大家有更優(yōu)的時間、空間復(fù)雜度方法，歡迎評論區(qū)交流。

最后，感謝您的閱讀，如果感到有所收獲的話可以給博主點一個 ?? 哦。文章來源地址http://www.zghlxwxcb.cn/news/detail-743705.html

到了這里，關(guān)于【每日一題】數(shù)組中兩個數(shù)的最大異或值的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！