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

leetcode

题目

image.png

image.png

分析

这题难点在于nums的长度最大可到2*10^5，所以暴力求解时间复杂度O(N^2)的算法是会超时的。这题可以利用一个最大异或值的特点。

一

从二进制来看，我们希望一个值越大，肯定是想高位尽量为1的，

  • 比如一个数 0b1000，在0b0000与0b1111两个数中选一个来获取最大异或值，理应从高位来看，0b1000与0b0000异或会得到0b1xxx，那么这里基本就可以确定0b000是正解，而0b1111可以不考虑后面低位的异或值了，以为他高位与0b1000异或得到的是0b0xxx，是绝对比0b1xxx小的
  • 而且二进制每个位上只有0和1，所以一旦得出其中一个0b1xxx，后面都可以忽略，即使后面有0b0111，但在最高位的比较中，得出0b1xxx已经是我们最好的结果。

二

如果三个数，其中两个异或等于第三个，那么第三个数与其余任意一个数的异或值也是等于另外一个数的，并且他们三个数同时截取相同的高位也能成立，比如

  • 0b0011 ^ 0b0100 == 0b0111
  • 0b0011 ^ 0b0111 == 0b0100
  • 0b0100 ^ 0b0111 == 0b0011

把他们同时截取高两位也成立：

  • 0b00 ^ 0b01 == 0b01
  • 0b00 ^ 0b01 == 0b01
  • 0b01 ^ 0b01 == 0b00

结论

  • a ^ b == c
  • a ^ c == b
  • b ^ c == a
  • a >> 2 ^ b >> 2 == c >> 2
  • a >> 2 ^ c >> 2 == b >> 2
  • b >> 2 ^ c >> 2 == a >> 2

三

相同的两个数异或值为0

思路及代码（哈希表）

由于最大值为2^31 -1 ，所以把所有元素都按照31位二进制看待，要取到最高位，则要右移30位。然后假设在最高位能取到最大值1，然后根据上述分析一，如果该位能取到1，说明最大值该位也为1，即可停止寻找。如此重复31遍，即可得出最大异或值。

初步代码如下：

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
/**
 * @param {number[]} nums 0 <= nums[i] <= 2 ^ 31 - 1
 * @return {number}
 */
var findMaximumXOR = function (nums) {
  let heightBit = 30;
  let x = 0;
  // 取高位
  for (let k = heightBit; k >= 0; k -= 1) {
    // 假设能取到1
    x = (x << 1) + 1;
    let found = false;

    // 双循环判断是否能取到1
    for (let i = 0; i < nums.length; i += 1) {
      for (let j = i + 1; j < nums.length; j += 1) {
        if (((nums[i] >> k) ^ (nums[j] >> k)) == x) {
          found = true;
          break;
        }
      }
    }

    // 如果不能取到1，则取0
    if (!found) x -= 1;
  }
  return x;
};

这里j的循环从i+1开始是考虑到了上述分析三，但这里始终是使用了嵌套循环去寻找能否取到1，所以在leetcode中仍然是过不了的，会超出时间限制。

要解决这个问题，我们可以换个思路，用两个单独的循环取到(nums[i] >> k)和(nums[j] >> k)，并且用哈希表去存储我们的临时结果，代码如下：

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

/**
 * @param {number[]} nums 0 <= nums[i] <= 2 ^ 31 - 1
 * @return {number}
 */
var findMaximumXOR = function (nums) {
  // 碰碰运气
  if (nums.length <= 1) return 0;
  if (nums.length == 2) return nums[0] ^ nums[1];
  const HEIGHT_BIT = 30;
  let x = 0;
  for (let k = HEIGHT_BIT; k >= 0; k -= 1) {
    let set = new Set();
    for (let i = 0; i < nums.length; i += 1) {
      set.add(nums[i] >> k);
    }

    x = x * 2 + 1;
    let found = false;

    for (let i = 0; i < nums.length; i += 1) {
      if (set.has(x ^ (nums[i] >> k))) {
        found = true;
        break;
      }
    }

    if (!found) {
      x -= 1;
    }
  }

  return x;
};

可以看到，我们使用一个Set集合，利用其实例方法，做到了时间复杂度为O(n)的存与O(1)的取，时间复杂度也从指数级的O(n^2)变为O(n)。再加上K位的循环，整体的时间复杂度位O(n*log(C))，n为数组长度，C是元素的取值范围，log(C)表示元素二进制的位数。

0-1 Trie

虽然上述代码已经是我们能提交的最好的JavaScript代码了，但是还是需要了解一下这个数据结构，真正的精髓在于按二进制位取值，并且我们每次的x都是类似判断前缀的形式，对于这种问题，字典树是我们最理想的数据结构，哈希表的代码利用Set结构也能够做到判断前缀是否存在，但我们是每次都循环n去创建这么个Set结构的，而字典树不需要，字典树只需要一次录入我们的所有元素，就能提供startsWith方法来判断前缀，总体来说时间复杂度还是O(nlog(C))，但实际哈希表的方法是O(2n*log(C))，只是大O表示法忽略了系数。

但是JavaScript并没有这样的数据结构，我是自己实现了一个，并且是字符串操作的，实际的执行效率并不如上面的哈希表，但也放出来，大家可以学一学他的思想。

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
82
83
84
85
86
87
88
89
class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char);
    }
    node.isEndOfWord = true;
  }

  search(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        return false;
      }
      node = node.children.get(char);
    }
    return node.isEndOfWord;
  }

  startsWith(prefix) {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) {
        return false;
      }
      node = node.children.get(char);
    }
    return true;
  }
}

let arr1 = [
  0b00000011, 0b00001010, 0b00000101, 0b00011001, 0b00000010, 0b00001000,
];

let arr2 = [
  89, 102, 183, 233, 175, 87, 497, 350, 348, 191, 136, 497, 166, 420, 279, 212,
  269, 125, 262, 74,
];

/**
 * @param {number[]} nums 0 <= nums[i] <= 2 ^ 31 - 1
 * @return {number}
 */
var findMaximumXOR = function (nums) {
  const HEIGHT_BIT = 30;

  let trie = new Trie();
  for (let i = 0; i < nums.length; i += 1) {
    let num = nums[i].toString(2).padStart(HEIGHT_BIT + 1, "0");
    trie.insert(num);
  }

  let x = 0;
  for (let k = HEIGHT_BIT; k >= 0; k -= 1) {
    let found = false;
    x = x * 2 + 1;
    for (let i = 0; i < nums.length; i += 1) {
      let prefix = (x ^ (nums[i] >> k))
        .toString(2)
        .padStart(HEIGHT_BIT - k + 1, "0");
      if (trie.startsWith(prefix)) {
        found = true;
        break;
      }
    }

    if (!found) x -= 1;
  }
  return x;
};

console.log(findMaximumXOR(arr2));

可以看到，我们再二进制位k的循环外，录入了一次元素进字典树，相比哈希表是少循环了大概29次吧，哈哈哈。