題目來(lái)源
感覺(jué)很巧妙的一道題便锨，一個(gè)數(shù)組中，任取兩個(gè)元素我碟，求最大的異或和放案，要求O(n)的做法。我這種渣渣只能想到n方的做法…
看了好久答案才理解矫俺。
首先了解一個(gè)知識(shí)點(diǎn)吱殉，假如
A XOR B = C then
A XOR C = B and
B XOR C = A
然后整數(shù)類型最多31位，所以從高往低恳守，用&操作來(lái)截取高位考婴，然后通過(guò)上面這個(gè)知識(shí)點(diǎn)來(lái)判斷當(dāng)前位是否存在兩個(gè)數(shù)異或使得當(dāng)前位為1，并且高位的那些還是保持原來(lái)的催烘。
class Solution {
public:
int findMaximumXOR(vector<int>& nums) {
int mask = 0, maximum = 0;
for (int i=31; i>=0; i--) {
mask |= 1 << i;
unordered_set<int> prefixs;
for (auto num : nums)
prefixs.insert(num & mask);
int tmp = maximum | 1 << i;
for (auto prefix : prefixs)
if (prefixs.count(tmp ^ prefix)) {
maximum = tmp;
break;
}
}
return maximum;
}
};
