leetcode_421数组中两个数的最大异或值

1. 题意

求数组中两个数的最大异或值

数组中两个数的最大异或值

2. 题解

2.1 哈希表

$a_i\oplus a_j=x$
所以
$a_i=x\oplus a_j$

考虑$a_i、a_j$的每一位的所有情况

我们可以从最高位开始尝试，是否能使第$k$位为1。

即对$pre(k,a_j)$，$preSet(k)$中是否有$x\oplus pre(k,a_j)$使得枚举的最大前缀$x$成立。

• 代码

class Solution {
public:

   

    int findMaximumXOR(vector<int>& nums) {

        int ans = 0;
        for ( int i = 30; i > -1; --i ) {

            unordered_set<int> preSet;

            for ( int num: nums) {
                preSet.insert( num >> i);
            }

            ans = ans << 1 | 1;
            bool find = false;
            for (int num: nums) {
                if ( preSet.count( (num >> i) ^ ans )) {
                    find = true;
                    break;
                }
            }
            if ( !find)
                ans--;

        }     
        


        return ans;
    }
};
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

2.2 前缀树

可以将所有值插入到一颗0-1前缀树中，然后再遍历每个值，对于每一位尽量选择它的翻转值，如果
树中有该路径的话。最后再取最大值。

class Solution {
public:

    class Trie {
    public:
        Trie():isEnd(false),left(nullptr),right(nullptr)
        {}

        void insert(int v) {
            Trie *cur = this;


            for ( int bit = 30; bit > -1; --bit) {
                int c = (1 << bit) & v;

                if (!c) {
                    
                    if (cur->left == nullptr) {
                        cur->left = new Trie();
                    }
                    cur = cur->left;
                }
                else {
                    if ( cur->right == nullptr)
                        cur->right = new Trie();
                    cur = cur->right;
                }
            }
            cur->isEnd = true;
        }
        int getMaxXor(int v) {

            int ans = 0;
            Trie *cur = this;
            for ( int bit = 30; bit > -1; --bit) {
                int c = (1 << bit) & v;

                if (c) {
                    if ( cur->left) {
                        cur = cur->left;
                        ans |= (1 << bit);
                    }
                    else {
                        cur = cur->right;
                    }
                }
                else {
                    if ( cur->right ) {
                        cur  = cur->right;
                        ans |= (1 << bit);
                    }
                    else {
                        cur = cur->left;
                    }
                }
            }

            return ans; 
        }

    private:
        Trie *left;
        Trie *right;
        bool isEnd;
    };

    int findMaximumXOR(vector<int>& nums) {
        
        Trie trie;
        for (int num: nums)
            trie.insert(num);

        int ans = 0;

        for (int num:nums) {
            ans = max(ans, trie.getMaxXor(num) );
        }

        return ans;
    }
};
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81