Description:

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.

Link:

https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/description/

解題方法：

在解題之前棉圈，首先要了解2個事情：

1. 兩個數(shù)XOR的結(jié)果取決于這兩位數(shù)的二進(jìn)制形式每一位是否相同畏纲。當(dāng)相同時焕檬，結(jié)果在這一位上為0；當(dāng)不同時，結(jié)果在這一位上為1。
2. 假設(shè)我們有3個數(shù)：a, b, c；當(dāng)a 和 b以及b和c在第1位上有不同時（a和c相同），那么最大的XOR只會出現(xiàn)在aXORb與bXORc之間邑时。

解題方法：

1. 我們將數(shù)組里面的元素分組奴紧，以第一次出現(xiàn)不同的位置分為set0和set1兩組，進(jìn)入遞歸函數(shù)（set0, set1, poi - 1）晶丘；
2. 將在set0和set1中的數(shù)根據(jù)下一位(poi)的值各自再分為兩組set01和set00, set10和set11黍氮；
3. 當(dāng)set01和set10或者set00和set11同時存在時，意味著最大的XOR值在這一位上必定為1浅浮，在這層遞歸中最大XOR值=1<<poi + max(下一層遞歸(set01, set10, poi - 1),下一層遞歸(set00, set11, poi - 1))沫浆；如果這兩組都不存在，則將位置向右再移一位滚秩，重復(fù)進(jìn)行操作2专执；

Time Complexity：

O(N)

完整代碼：

class Solution 
{
public:
    int findMaximumXOR(vector<int>& nums) 
    {
        int result = 0;
        vector<int> set0;
        vector<int> set1;
        for(int poi = 31; poi >= 0; poi--)
        {
            set0.clear();
            set1.clear();
            for(int i: nums)
            {
                if(i & (1 << poi))
                    set1.push_back(i);
                else
                    set0.push_back(i);
            }
            if(!set0.empty() && !set1.empty())
            {
                result += (1 << poi);
                result += helper(set0, set1, poi - 1);
                break;
            }
        }
        return result;
        
    }
    int helper(vector<int>& set0, vector<int>& set1, int poi)
    {
        if(poi < 0)
            return 0;
        int result = 0;
        vector<int> set00;
        vector<int> set01;
        vector<int> set10;
        vector<int> set11;
        for(int i : set0)
        {
            if(i & (1 << poi))
                set01.push_back(i);
            else
                set00.push_back(i);
        }
        for(int i : set1)
        {
            if(i & (1 << poi))
                set11.push_back(i);
            else
                set10.push_back(i);
        }
        int temp0 = 0, temp1 = 0;
        if(!set00.empty() && !set11.empty())
        {
            temp0 = (1 << poi) +  helper(set00, set11, poi - 1);  //參數(shù)的順序不能出錯
        }
        if(!set01.empty() && !set10.empty())
        {
            temp1 =(1 << poi) + helper(set01, set10, poi - 1);  //參數(shù)的順序不能出錯
        }
        if(temp0 || temp1)
        {
            return result += max(temp0, temp1);
        }
        else
            return helper(set0, set1, poi - 1);
    }
};