# LeetCode-Maximum XOR of Two Numbers in an Array
Date: 2021-02-27


### **问题：**

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. 穷举

将所有情况进行穷举，时间复杂度O(n2) ，不过不符合题目要求

```
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树

时间复杂度O(n), 不过需要提前构建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]
```

### **参考及引用**

图片来源 twitter Ice Angel @addyiceangel