# LeetCode-Maximum XOR of Two Numbers in an Array

### 问题：

Given an integer array `nums`, return the maximum result of `nums[i] XOR nums[j]`, where `0 ≤ i ≤ j < n`.

Follow up: Could you do this in `O(n)` runtime?

Example 1:

Input:

``` nums = [3,10,5,25,2,8]
```

Output:

``` 28
```

Explanation:

Constraints:

• `1 <= nums.length <= 2 * 10`4
• `0 <= nums[i] <= 2`31` - 1`

### 解答：

1. 穷举

```class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
maxXor = 0
n = len(nums)
for i in range(n):
for j in range(i+1, n):
maxXor = max(maxXor, nums[i]^nums[j])
return maxXor'''```
1. Trie树

```class Trie:
def __init__(self):
self.children = [None]*2

class Solution:
def __init__(self):
self.root = Trie()

def findMaximumXOR(self, nums: List[int]) -> int:
for num in nums:
self.insert(num)
res = 0
for num in nums:
res = max(res, self.findMaxXOR(num))
return res

def findMaxXOR(self, num):
res = 0
node = self.root
for i in range(31, -1, -1):
bit = (num >> i) & 1
if node.children[bit^1] is None:
node = node.children[bit]
else:
node = node.children[bit^1]
res |= 1<<i
return res

def insert(self,num):
node = self.root
for i in range(31, -1, -1):
bit = (num >> i) & 1
if node.children[bit] is None:
node.children[bit] = Trie()
node = node.children[bit]```