问题：

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:

1

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

Output:

1

 28

Explanation:

Constraints:

  • 1 <= nums.length <= 2 * 104
  • 0 <= nums[i] <= 231 - 1

解答：

  1. 穷举

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

1
2
3
4
5
6
7
8

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树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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