两重循环，得出结果，结果题目中问能不能在$\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;
}
};