Leetcode 421. Maximum XOR of Two Numbers in an Array

Seawolf

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

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. class Solution:
   
2.     def findMaximumXOR(self, nums: List[int]) -> int:
   
3.         # Compute length L of max number in a binary representation
   
4.         L = len(bin(max(nums))) - 2
   
5.         # zero left-padding to ensure L bits for each number
   
6.         nums = [[(x >> i) & 1 for i in range(L)][::-1] for x in nums]
   
7.         
   
8.         max_xor = 0
   
9.         trie = {}
   
10.         for num in nums:
    
11.             node = trie
    
12.             xor_node = trie
    
13.             curr_xor = 0
    
14.             for bit in num:
    
15.                 # insert new number in trie
    
16.                 if not bit in node:
    
17.                     node[bit] = {}
    
18.                 node = node[bit]
    
19.                
    
20.                 # to compute max xor of that new number
    
21.                 # with all previously inserted
    
22.                 toggled_bit = 1 - bit
    
23.                 if toggled_bit in xor_node:
    
24.                     curr_xor = (curr_xor << 1) | 1
    
25.                     xor_node = xor_node[toggled_bit]
    
26.                 else:
    
27.                     curr_xor = curr_xor << 1
    
28.                     xor_node = xor_node[bit]
    
29.                     
    
30.             max_xor = max(max_xor, curr_xor)
    
31. 
    
32.         return max_xor

复制代码