数组中两个数异或求最大值

特别说明：本文转载自lingen1949 大神的文章，按照个人理解增加了部分注释，感谢大神提供思路。在此附上原文链接：

http://blog.csdn.net/lingen1949/article/details/52873656

题目要求：

421. Maximum XOR of Two Numbers in an Array

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.

Could you do this in O(n) runtime?

Example:

Input: [3, 10, 5, 25, 2, 8]

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.

思路一:

利用a ^ b = c，而a ^ b ^ b = a, 则 c ^ b = a.

int findMaximumXOR(vector<int>& nums) {
	if (nums.size() < 2) return 0;
	int maxNum = 0;
	int flag = 0;
	//本题关键在于，最终最大的异或结果一定是由所有数中，高位最先为1的数（也就是最大的数）参与得到的。
	for (int i = 31; i >= 0; --i)
	{//从最大值maxNum最高位到最低位开始确定</span>  
		set<int> hash;

		flag |= (1 << i);    //利用flag取出每一个x的前n-i位，n为31
		for (int x : nums)
		{

			hash.insert(flag & x);   //将取出来的每一种前n-i位存入到集合中，以备接下来比较。
		}

		int tmp = maxNum | (1 << i);  //maxNum为上一次比较得出的前n-i位最大的数值，利用tmp尝试，若紧邻的下一位为1，是否有可能？
		for (int x : hash)
		{
			//此处用到了x1^tmp=x2,则x1^x2=tmp.原因：x1^tmp=x2,两边同时异或x1,则tmp=x1^x2.
			if (hash.find(x ^ tmp) != hash.end())  //如果存在，就说明有一个数的前n-i位与另一个数的前n-i位异或结果为该maxNum
			{
				maxNum = tmp;
				break;
			}
		}
	}
	return maxNum;
}

思路二:

Tire树,利用nums中的数构建tire树,然后依次查找数组nums中数的异或最大值

    struct Node{  
        Node * next[2];  
        Node()  
        {  
            next[0] = nullptr;  
            next[1] = nullptr;  
        }  
    };  
       
    void buildTireTree(Node* root, int x)  
    {  
        for( int i = 31; i >= 0; --i )  
        {  
            int flag =  ( x & (1<<i) ) ? 1 : 0;  
            if( root->next[flag] == nullptr )  
            {  
                root->next[flag] = new Node();  
            }  
            root = root->next[flag];  
        }  
    }  
      
    int findMaxXorInTire(Node* root, int x)  
    {  
        int result = 0;  
          
        for( int i = 31; i >= 0; --i )  
        {  
   
            int flag = ( x & ( 1<<i) )? 0: 1;  
            if( root->next[flag] != nullptr )  
            {  
                result |= (1<<i);  
                root = root->next[flag];  
            }  
            else  
                root = root->next[1-flag];  
        }  
        return result;  
    }  
      
public:  
    int findMaximumXOR(vector<int>& nums) {  
       if( nums.size() < 2 ) return 0;  
       Node head;  
       for( int x: nums )  
       {  
           buildTireTree( &head, x );  
       }  
         
       int maxNum = 0;//INT_MIN;  
       for( int x: nums )  
       {  
           int m = findMaxXorInTire( &head, x );  
           maxNum = max( maxNum, m );  
       }  
       return maxNum;  
         
    }