Leetcode 421

发表于 分类于 ，

Leetcode 421

Description

给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

进阶：你可以在 O(n) 的时间解决这个问题吗？

Sample

Sample 1

1
2
3
输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.

Sample 2

1
2
输入：nums = [0]
输出：0

Sample 3：

1
2
输入：nums = [2,4]
输出：6

Sample 4：

1
2
输入：nums = [8,10,2]
输出：10

Sample 5：

1
2
输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127

Hint

  • 1 <= nums.length <= 2 * 10^4
  • 0 <= nums[i] <= 2^31 - 1

Solution

非常nice的一道题目，暴力肯定不可取，平方的复杂度不能接受。因为题目要求的是异或运算的结果，所以肯定是从二进制出发来考虑问题。

非常trivial的一个想法，优先使高位的结果为1，x xor y等于1，需要x和y不相同，所以很自然的，我们将所有数字按照第b位分成两组，如果两组都不为空，那么显然z的第b位一定可以等于1，接下来继续考虑b-1位。

当然这么递归就把问题搞麻烦了，导致x和y都一直在变，我们可以固定一个x=nums[i]，然后在nums[0]..nums[i-1]里面挑选y使得结果最大。

所以我们需要维护一个数据结构，能够快速添加一个数字，并且根据二进制位查询数字，可以根据二进制建立索引树，从高位向低位，这也是一个前缀树Trie，是IntTrie的一种，HAMT的思想与之类似。

Code

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
struct Node {
    Node *lc, *rc;

    Node () : lc(nullptr), rc(nullptr) {}
};

class IntTrie {
private:
    Node * root;
public:
    IntTrie () {
        root = new Node();
    }

    void insert(int num) {
        Node * t = root;
        for (int i = 30; i >= 0; --i) {
            if ((num & (1 << i)) == 0) {
                if (t->lc == nullptr)
                    t->lc = new Node();
                t = t->lc;
            }
            else {
                if (t->rc == nullptr)
                    t->rc = new Node();
                t = t->rc;
            }
        }

    }

    int ask(int num) const {
        Node * t = root;
        int ret = 0;
        for (int i = 30; i >= 0; --i) {
            if (num & (1 << i)) {
                if (t->lc != nullptr) {
                    ret |= (1 << i);
                    t = t->lc;
                }
                else
                    t = t->rc;
            }
            else {
                if (t->rc != nullptr) {
                    ret |= (1 << i);
                    t = t->rc;
                }
                else
                    t = t->lc;
            }
        }
        return ret;
    }
};

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        IntTrie t;
        int ret = 0;
        for (int v : nums) {
            t.insert(v);
            ret = max(ret, t.ask(v));
        } 
        return ret;
    }
};