Leetcode 421 Maximum Xor of Two Numbers in an Array

两重循环,得出结果,结果题目中问能不能在$\mathcal{O}(n)$时间内解决。也对,两重循环也没意思。

不过,还是先试试,最容易想到的算法结果怎么样,这个算法的时间复杂度是$\mathcal{O}(n^2)$。自己亦或自己的结果是0,所以初始化res = 0就包括了所有i = j的情况。

不出所料,这个方法超时,为了避免一些像我这样的人直接复制粘贴到错误答案,我将超时方法放在最后面。

那么就考虑亦或的性质,看看什么样的两个数,亦或起来能使结果最大。数中的某一位亦或,相同结果为0,不同为1 。那么两个数的二进制表示的“差异"越大,其亦或的结果的值越大。高位的差异重要性大于低位的差异。那么拿到一个数,将这个数取反,再与之亦或,得到的数一定是最大的。但是这个数不一定存在,那么我们就寻找这个取反得到的数的类似的数。

以下两种方法都来自互联网。

// Author: Huahua
class Trie {
public:
  Trie(): children(2) {}  
  vector<unique_ptr<Trie>> children;
};
class Solution {
public:
  int findMaximumXOR(vector<int>& nums) {
    Trie root;
    
    // Insert a number into the trie.
    auto insert = [&](Trie* node, int num) {
      for (int i = 31; i >= 0; --i) {
        int bit = (num >> i) & 1;
        if (!node->children[bit])
          node->children[bit] = std::make_unique<Trie>();
        node = node->children[bit].get();
      }
    };
  
    // Find max xor sum of num and another element in the array.
    auto query = [&](Trie* node, int num) {
      int sum = 0;
      for (int i = 31; i >= 0; --i) {
        int bit = (num >> i) & 1;
        if (node->children[1 - bit]) {
          sum += (1 << i);
          node = node->children[1 - bit].get();
        } else {
          node = node->children[bit].get();
        }
      }
      return sum;
    };
    
    // Insert all numbers.
    for (int x : nums) 
      insert(&root, x);
    
    int ans = 0;
    // For each number find the maximum xor sum.
    for (int x : nums) 
      ans = max(ans, query(&root, x));
    return ans;
  }
};
static int x = [] () {ios::sync_with_stdio(false); cin.tie(0); return 0;} ();
class Solution {
 public:
  int findMaximumXOR(vector<int>& nums) {
    int res = 0, mask = 0;
    for (int i=31; i>=0; --i) {
      mask |= (1 << i);
      unordered_set<int> s;
      for (const int num: nums)
        s.insert(num & mask);
      int t = res | (1 << i);
      for (const int prefix: s)
        if (s.count(t ^ prefix)) {
          res = t;
          break;
        }
    }
    return res;
  }
};

简单的思考,简单的代码,不简单的计算耗时。

class Solution_TLE {
 public:
  int findMaximumXOR(vector<int>& nums) {
    int res = 0;     
    for (int i = 0, n = nums.size(); i < n; ++i)
      for (int j = i + 1; j < n; ++j)
        res = max(res, nums[i] ^ nums[j]);
    return res;
  }
};

#直达链接

LeetCode 421. Maximum XOR of Two Numbers in an Array