題目： LeetCode - 421. Maximum XOR of Two Numbers in an Array

題目說明

給一個陣列，找出陣列中最大的任意兩者互斥或的值。

解題思路

由於互斥或有 a ^ b = c -> a ^ c = b 的特性，所以可以先找出一個最大值，接著遍歷陣列查看 val ^ 最大值 是否存在，若存在表示這個最大值是可以被陣列中兩數互斥或出來的。由於要找最大值，所以要讓二進制中最高位盡可能為 1，因為只需要判斷最高位，所以我們需要一個 mask，接著將陣列中過遮罩的值存入 unordered_set，最後遍歷 set 查看 val ^ (ret | i) 是否存在即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findMaximumXOR(vector<int>& nums)
    {
        int ret{}, mask{};
        for(int i = 1 << 30; i; i >>= 1)
        {
            mask |= i;
            unordered_set<int> u_set;
            for(auto num : nums) u_set.insert(mask & num);
            for(auto val : u_set) if(u_set.count(val ^ (ret | i))) { ret |= i; break; }
        }
        return ret;
    }
};