马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
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.
class Solution:
def findMaximumXOR(self, nums: List[int]) -> 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[bit] = {}
node = node[bit]
# 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[toggled_bit]
else:
curr_xor = curr_xor << 1
xor_node = xor_node[bit]
max_xor = max(max_xor, curr_xor)
return max_xor
|