leetcode 421 Maximum XOR of Two Numbers in an Array
z
 2019-06-04 19:51:53  

Given a non-empty array of numbers, $a_0, a_1, …, a_{n-1}$, where $0 \le a_i \le 2^{32}$.

Find the maximum result of $a_i \ \text{xor} \ a_j$, where 0 ≤ i, j < n.

Could you do this in O(n) runtime?

Example:

1
2
3
4
5
Input: [3, 10, 5, 25, 2, 8]

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.
  • 用树状结构来保存每一个数。
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Node:
    zero = None
    one = None
        
class Solution(object):
    
    def add(self, root, i):
        node = root
        for j in range(31, -1, -1):
            mask = 1 << j
            left = mask & i
            if left:
                if node.one == None:
                    node.one = Node()
                node = node.one
            else:
                if node.zero == None:
                    node.zero = Node()
                node = node.zero



    def find(self, root, i):
        ans = 0
        node = root
        for j in range(31, -1, -1):
            mask = 1 << j
            left = i & mask
            if node.one and node.zero:
                if left:
                    node = node.zero
                if not left:
                    node = node.one
                ans += mask
            else:
                if (node.one and not left) or (node.zero and left):
                    ans += mask
                node = node.one or node.zero

        return ans



    def findMaximumXOR(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        root = Node()
        ans = 0
        max_left = 0
        candidate = []
        for i in nums:
            self.add(root, i)
            left = math.ceil(0 if i == 0 else math.log(i, 2))
            if left == max_left:
                candidate.append(i)
            if left > max_left:
                max_left = left
                candidate = []
                candidate.append(i)
                
        for i in nums:
            ans = max(ans, self.find(root, i))
        return ans