421 Maximum XOR of Two Numbers in an Array

Search…

421. Maximum XOR of Two Numbers in an Array​
1. Question
Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai< 231.
Find the maximum result of aiXOR aj, where 0 ≤i,j<n.
Could you do this in O(n) runtime?
Example:
1
Input: [3, 10, 5, 25, 2, 8]
2
​
3
Output: 28
4
​
5
Explanation: The maximum result is 5 ^ 25 = 28.
Copied!
2. Implementation
(1) Brute Force
1
class Solution {
2
    public int findMaximumXOR(int[] nums) {
3
        if (nums == null || nums.length == 0) {
4
            return 0;
5
        }
6
​
7
        int max = 0;
8
​
9
        for (int i = 0; i < nums.length; i++) {
10
            for (int j = i + 1; j < nums.length; j++) {
11
                max = Math.max(max, nums[i] ^ nums[j]);
12
            }
13
        }
14
        return max;
15
    }
16
}
Copied!
(2) Bit Manipulation + Trie
1
class Solution {
2
    class TrieNode {
3
        TrieNode[] childNode;
4
​
5
        public TrieNode() {
6
            childNode = new TrieNode[2];
7
        }
8
    }
9
​
10
    class Trie {
11
        TrieNode root;
12
​
13
        public Trie() {
14
            root = new TrieNode();
15
        }
16
​
17
        public void insert(int num) {
18
            TrieNode curNode = root;
19
            for (int i = 31; i >= 0; i--) {
20
                int bit = (num >>> i) & 1;
21
​
22
                if (curNode.childNode[bit] == null) {
23
                    curNode.childNode[bit] = new TrieNode();
24
                }
25
                curNode = curNode.childNode[bit];
26
            }
27
        }
28
    }
29
​
30
    public int findMaximumXOR(int[] nums) {
31
        if (nums == null || nums.length == 0) {
32
            return 0;
33
        }
34
​
35
        Trie trie = new Trie();
36
​
37
        for (int num : nums) {
38
            trie.insert(num);
39
        }
40
​
41
        int max = 0;
42
​
43
        for (int num : nums) {
44
            int curSum = 0;
45
            TrieNode curNode = trie.root;
46
​
47
            for (int i = 31; i >= 0; i--) {
48
                int bit = (num >>> i) & 1;
49
​
50
                if (curNode.childNode[bit ^ 1] != null) {
51
                    curSum |= (1 << i);
52
                    curNode = curNode.childNode[bit ^ 1];
53
                }
54
                else {
55
                    curNode = curNode.childNode[bit];
56
                }
57
            }
58
​
59
            max = Math.max(max, curSum);
60
        }
61
        return max;
62
    }
63
}
Copied!
3. Time & Space Complexity
Brute Force: 时间复杂度O(n^2), 空间复杂度O(1)
Bit Manipulation + Trie: 时间复杂度O(n), 空间复杂度O(n)

336 Palindrome Pairs

472 Concatenated Words

Last modified 2yr ago

Copy link

Contents

421. Maximum XOR of Two Numbers in an Array

1. Question

2. Implementation

3. Time & Space Complexity

421. Maximum XOR of Two Numbers in an Array​

1. Question

2. Implementation

3. Time & Space Complexity

421. Maximum XOR of Two Numbers in an Array