Leetcode 421. Maximum XOR of Two Numbers in an Array
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:
Output: 28
Explanation: The maximum result is 5 ^ 25 = 28.
class Solution:
def findMaximumXOR(self, nums: List) -> int:
# Compute length L of max number in a binary representation
L = len(bin(max(nums))) - 2
# zero left-padding to ensure L bits for each number
nums = [[(x >> i) & 1 for i in range(L)][::-1] for x in nums]
max_xor = 0
trie = {}
for num in nums:
node = trie
xor_node = trie
curr_xor = 0
for bit in num:
# insert new number in trie
if not bit in node:
node = {}
node = node
# to compute max xor of that new number
# with all previously inserted
toggled_bit = 1 - bit
if toggled_bit in xor_node:
curr_xor = (curr_xor << 1) | 1
xor_node = xor_node
else:
curr_xor = curr_xor << 1
xor_node = xor_node
max_xor = max(max_xor, curr_xor)
return max_xor
页:
[1]