LeetCode 421. 数组中两个数的最大异或值

思路

1. 将数组中的数全部存入字典树中
2. 遍历树中的每一个数在字典树中异或的最大结果，最后再求最大结果里面的最大值返回

代码实现

 1 class Solution {
 2     class Trie {
 3         public:
 4             Trie* next[2] = {NULL};
 5 
 6             //在字典树中插入数字num的二进制
 7             void insert(int num) {
 8                 Trie* t = this;
 9                 //因为元素小于2^31, 所以右移移30位即可到达最高位
10                 for(int i = 30; i >= 0; --i) {
11                     //取出num的每一位二进制
12                     int b = (num >> i) & 1;
13                     if(t->next[b] == NULL)
14                         t->next[b] = new Trie();
15                     t = t->next[b];
16                 }
17             }
18     };
19 public:
20     int findMaximumXOR(vector<int>& nums) {
21         Trie* root = new Trie();
22         for(int num: nums)
23             root->insert(num);
24         
25         int res = 0;
26         for(int num: nums) {
27             Trie* t = root;
28             int sum = 0;
29             for(int i = 30; i >= 0; --i) {
30                 int b = (num >> i) & 1;
31                  //如果b==1则贪心的去找0异或,否则找1异或
32                 if(b == 1) {
33                     if(t->next[0] != NULL) {
34                         sum += 1 << i;
35                         t = t->next[0];
36                     } else {
37                         //sum += 0;
38                         t = t->next[1];
39                     }    
40                 } else {
41                     if(t->next[1] != NULL) {
42                         sum += 1 << i;
43                         t = t->next[1];
44                     } else {
45                         //sum += 0;
46                         t = t->next[0];
47                     }
48                 }
49             }
50             //更新最大值
51             if(sum > res)
52                 res = sum;
53         }
54         return res;
55     }
56 };

复杂度分析

参考

力扣官方题解-数组中两个数的最大异或值

数组中两个数的最大异或值-前缀树+位运算+贪心