LC.P421[数组中两个数的最大异或值]

方法一：贪心+Trie

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
class Solution {
    public int findMaximumXOR(int[] nums) {
        Trie trie = new Trie();
        int ans = 0;
        for (int x : nums) {
            trie.insert(x);
            int y = trie.getVal(x);
            ans = Math.max(ans, x ^ y);
        }
        return ans;
    }

    private static class Trie {
        Trie[] next;

        public Trie() {
            next = new Trie[2];
        }

        public void insert(int x) {
            Trie node = this;
            for (int i = 31; i >= 0; --i) {
                int u = (x >> i) & 1;
                if (node.next[u] == null) {
                    node.next[u] = new Trie();
                }
                node = node.next[u];
            }
        }

        public int getVal(int x) {
            Trie node = this;
            int ans = 0;
            for (int i = 31; i >= 0; --i) {
                int a = (x >> i) & 1, b = 1 - a;
                if (node.next[b] != null) {
                    ans |= (b << i);
                    node = node.next[b];
                } else {
                    ans |= (a << i);
                    node = node.next[a];
                }
            }
            return ans;
        }
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

方法二：哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    // 利用性质： a ^ b = c ，则 a ^ c = b，且 b ^ c = a
    public int findMaximumXOR(int[] nums) {
        int res = 0, mask = 0;
        for (int i = 30; i >= 0; i--) {
            mask = mask | (1 << i);
            Set<Integer> set = new HashSet<>();
            for (int num : nums) {
                set.add(num & mask);
            }
            int temp = res | (1 << i);
            for (Integer prefix : set) {
                if (set.contains(prefix ^ temp)) {
                    res = temp;
                    break;
                }
            }
        }
        return res;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$