421. Maximum XOR of Two Numbers in an Array 数组中两个数的最大异或值

@TOC

# 题目描述

Given a non-empty array of numbers, `a0, a1, a2, … , an-1`, where `0 ≤ ai < 2^31`.

Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.

Could you do this in O(n) runtime?

Example:

``````Input: [3, 10, 5, 25, 2, 8]

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.
``````

# 解题方法

# 依次遍历每一位

``````1. i = 3, set = {1000, 0000} => max = 1000
2. i = 2, set = {1100, 1000, 0100, 0000} => max = 1100
3. i = 1, set = {1110, 1010, 0110, 0010} => max = 1100
4. i = 0, set = {1110, 1011, 0111, 0010} => max = 1100
``````

Python代码：

``````class Solution(object):
def findMaximumXOR(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
for x in range(32)[::-1]:
prefixSet = set([n & mask for n in nums])
temp = ans | 1 << x
for prefix in prefixSet:
if temp ^ prefix in prefixSet:
ans = temp
break
return ans
``````

C++代码：

``````class Solution {
public:
int findMaximumXOR(vector<int>& nums) {
int res = 0;
unordered_set<int> s;
for (int i = 31; i >= 0; i--) {
s.clear();
for (int num : nums) {
}
int tmp = res | (1 << i);
for (int pre : s) {
if (s.count(tmp ^ pre)) {
res = tmp;
break;
}
}
}
return res;
}
};
``````

# 日期

2018 年 3 月 7 日 2018 年 12 月 19 日 —— 感冒了，好难受