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

发表于 分类于 阅读次数： Waline： 本文字数： 161 阅读时长 ≈ 1 分钟

考点

  • 试填法
  • 位运算

题解

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
class Solution {
 public:
  int n, mx;
  unordered_set<int> st;
  // 找x的最高位下标，下标从低位0开始
  int findIdx(int x) {
    int res = 0, i = 0;
    while (x) {
      if (x & 1) res = i;
      i++, x >>= 1;
    }
    return res;
  }
  int findMaximumXOR(vector<int>& nums) {
    n = nums.size(), mx = 0;
    for (int i = 0; i < n; ++i) mx = max(mx, nums[i]);
    int idx = findIdx(mx), mask = 0, ans = 0;
    // 贪心地从最高位开始枚举可能性
    for (int i = idx; i >= 0; --i) {
      mask |= (1 << i);
      int t = ans | (1 << i);
      st.clear();
      for (int j = 0; j < n; ++j) {
        int x = mask & nums[j];
        if (st.find(x ^ t) != st.end()) {
          ans = t;
          break;
        } else {
          st.emplace(x);
        }
      }
    }
    return ans;
  }
};

思路

试填法的模板题，直接参考题解链接即可