[LeetCode]Maximum XOR of Two Numbers in an Array

XOR的运算法则是相同变0，不同变1。那么这道题的思路就是，对于每一个数，从高位到低位寻找每一位尽量不相同的数，这样可以让这个数和其他数XOR的结果最大。然后我们从这些值中取出最大值，就是我们要求的值。如何在O(1)的时间内寻找每一位尽量不同的数呢？Trie是一个很好的数据结构可以帮助我们实现，关于Trie的介绍可以参考这一片文章。具体思路就是，如果能找到和当前位数不同的就去对应的分支，否则就去另外一个。因为只有0和1可以选，只要trie不为空，当前节点只要没有0/1的子节点，就必然有另一个对应的节点，所有的数的bit位数都是一样的。时间复杂度，空间复杂度O(n)，代码如下：

	class Solution {
	public:
	int findMaximumXOR(vector<int>& nums) {
	int len = nums.size(), res = 0;
	Node* root = new Node();
	for(int i = 0; i < len; ++i)
	{
	int num = nums[i];
	if(i)
	{
	int currMax = 0;
	Node* curr = root;
	for(int k = 31; k >= 0; --k)
	{
	int target = (1 << k) & num? 0: 1;
	if(curr->children[target])
	{
	curr = curr->children[target];
	currMax |= (1 << k);
	}
	else
	curr = curr->children[1 - target];
	}
	res = max(res, currMax);
	}
	insert(root, num, 31);
	}
	return res;
	}
	private:
	struct Node
	{
	vector<Node*> children;
	Node()
	{
	children = vector<Node*>(2, nullptr);
	}
	};
	void insert(Node* root, int num, int idx)
	{
	while(idx >= 0)
	{
	int bit = (num >> idx) & 1;
	if(!(root->children)[bit])
	(root->children)[bit] = new Node();
	root = (root->children)[bit];
	--idx;
	}
	}
	};

view raw Maximum XOR of Two Numbers in an Array_II.cpp hosted with ❤ by GitHub

当然之前为了省事，尝试过直接用set来解决，具体的思路是一样的，先贴代码（这个代码是错误的）：

	class Solution {
	public:
	int findMaximumXOR(vector<int>& nums) {
	int len = nums.size(), res = 0;
	unordered_set<int> set;
	for(int i = 0; i < len; ++i)
	{
	int mask = 0, num = nums[i], currMax = 0;
	//can't write code in this way
	//for example, we finish process num, it has prefix 1000 0000 0000 0000, 1100 0000 0000 0000...
	//but when we find in set again, it will think we have a number start with 10...., since we have 1000 0000 0000 0000
	//in our set. We may not have number start with 10... actually.
	//So we need to follow steps to process all prefix with length 1 then 2...
	for(int j = 31; j >= 0; --j)
	{
	mask |= (1 << j);
	int prefix = mask & num;
	set.insert(prefix);
	if(i)
	{
	int target = currMax | (1 << j);
	//a ^ b = c --> c * b = a
	if(set.find(target ^ prefix) != set.end())
	currMax = target;
	}
	}
	res = max(res, currMax);
	}
	return res;
	}
	};

view raw Maximum XOR of Two Numbers in an Array_failed.cpp hosted with ❤ by GitHub

但是这段代码却无法得到我们想要的结果，原因注释中已经说明。因为set存有所有的前缀，但我们再retrieve的时候无法区分这个是长度为多少的前缀，如果长度为2的前缀被认为长度为3的前缀就会有问题。但是Trie就不存在这方面的问题。
当然并不是说用set就没法做，我们只需要每次处理长度为k的prefix，之后清空set接着处理长度为k + 1的prefix就可以了，时间复杂度O(n)，空间复杂度O(n)，代码如下：

	class Solution {
	public:
	int findMaximumXOR(vector<int>& nums) {
	int len = nums.size(), res = 0, mask = 0;
	for(int i = 31; i >= 0; --i)
	{
	mask |= (1 << i);
	unordered_set<int> set;
	for(auto& num : nums)
	set.insert(mask & num);
	int target = res | (1 << i);
	for(auto prefix : set)
	{
	//a ^ b = c --> c * b = a
	if(set.find(prefix ^ target) != set.end())
	{
	res = target;
	break;
	}
	}
	}
	return res;
	}
	};

view raw Maximum XOR of Two Numbers in an Array_I.cpp hosted with ❤ by GitHub