LeetCode 421. 数组中两个数的最大异或值（Trie树）

Michael阿明

发布于 2020-07-13 15:31:39

1.2K0

发布于 2020-07-13 15:31:39

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

1. 题目

给定一个非空数组，数组中元素为 a0, a1, a2, … , an-1，其中 0 ≤ ai < 231 。

找到 ai 和aj 最大的异或 (XOR) 运算结果，其中0 ≤ i, j < n 。

你能在O(n)的时间解决这个问题吗？

示例:

输入: [3, 10, 5, 25, 2, 8]

输出: 28

解释: 最大的结果是 5 ^ 25 = 28.

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. Tries树

题目要求O(n)时间复杂度，两两异或O(n2)
考虑将每个数字的二进制位插入Trie树（从高位往低位插入）O(n)
再遍历每个数字bit，贪心从trie树的异或最大路径往下走，得到一个val，取val的最大值，O(n)时间复杂度

class Node
{
public:
	int val;
	Node *next[2];
	Node(int v = 0):val(v) {next[0] = next[1] = NULL;}
};
class Trie
{
public:
	Node *root;
	Trie()
	{
		root = new Node();
	}
	~Trie()//析构释放内存
	{
		destroy(root);
	}
	void destroy(Node *root)
	{
		if(root == NULL)
			return;
		destroy(root->next[0]);
		destroy(root->next[1]);
		delete root;
	}
	void insert(int n)//插入数字的二进制位
	{
		Node *cur = root;
		int bit;
		for(int i = 31; i >= 0; --i)
		{
			bit = (n>>i) & 1;
			if(cur->next[bit] == NULL)
				cur->next[bit] = new Node(bit);
			cur = cur->next[bit];
		}
	}
	int MaxXOR(int n)
	{
		Node *cur = root;
		int val = 0, bit, anotherBit;
		for(int i = 31; i >= 0; --i)
		{
			bit = (n>>i) & 1;
			anotherBit = bit^1;//取反
			if(cur->next[anotherBit])
			{
				val += (1<<i);
				cur = cur->next[anotherBit];
			}
			else
				cur = cur->next[bit];
		}
		return val;
	}
};
class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        Trie tree;
        int ans = INT_MIN;
        for(int n:nums)
        	tree.insert(n);
        for(int n:nums)
        	ans = max(ans,tree.MaxXOR(n)); 
        return ans;
    }
};