本文共 1069 字，大约阅读时间需要 3 分钟。

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: 28Explanation: The maximum result is 5 ^ 25 = 28.

----------------------------------------------------------------------------------------

Cycle bit by bit. For every bit, we could know the largest prefix expected. If the expected largest prefix could be xor by some two nums (implemented by hashSet), we could know the final answer. The complexity is O(n)

class Solution:    def findMaximumXOR(self, nums):        pre, mask = 0, 0        for i in range(31, -1, -1):            one = (1 << i)            mask |= one            exist = set()            cur_largest = pre | one            for num in nums:                cur = num & mask                if ((cur ^ cur_largest) in exist):                    pre = cur_largest                else:                    exist.add(cur)        return pres = Solution()print(s.findMaximumXOR([3, 10, 5, 25, 2, 8]))

转载地址：http://wtfoi.baihongyu.com/