C++ 69ms Trie (binary tree) based solution


  • 0
    J

    It is essentially a Trie based approach, But I don't know if C++ has built-in Trie class. Therefore I implement it myself.
    Let 'k' be the highest bit such that elements differ, and let those elements be G0 and G1 respectively. Definitely the optimal answer is the XOR of an ele from G0 and an ele from G1. Then we consider the next bit, and have groups G00, G01, G10, G11 respectively. The optimal solution must come from one of the following pairs: (G00,G11),(G01,G10). What if we do not have G10 and G00? Then we consider (G010,G111) (G011,G110) and so on. We only store elements in leaves.

    My solution should be O(n), but my implementation makes it hard to analyze the time complexity of searching. I think the pre-termination prevents the search to be exponential.

    PS. we don't destruct the tree for simplicity.

    struct bitTreeNode
    {
        int nums;
        bitTreeNode *left, *right;
    };
    class Solution {
    public:
        int findMaximumXOR(vector<int>& nums) {
            int n = nums.size();
            if (n<1)
                return 0;
            if (n==1)
                return 0;
            if (n==2)
                return (nums[0] ^ nums[1]);
            // to get the bitBase
            vector<int> bitBase(31,1);
            for (int i=1; i<31; i++)
                bitBase[i] = (bitBase[i-1]<<1);
            int highestBit = 31;
            bool bitOK[] = {0,0};
            // linear time
            while (highestBit>0)
            {
                bitOK[0] = bitOK[1] = 0;
                for (int i=0; i<n; i++)
                {
                    bitOK[(nums[i] & bitBase[highestBit-1])==0] = 1;
                }
                if (bitOK[0] && bitOK[1])
                    break;
                highestBit--;
            }
            if (highestBit==0)  // all numbers are the same
                return 0;
            vector<int>::iterator it = unique (nums.begin(), nums.end());
            nums.resize(distance(nums.begin(),it) );
            n = nums.size();
            // optimal solution must be across group
            bitTreeNode *ptr = new bitTreeNode;
            ptr->nums = -1;
            vector<int> tempNums = nums;
            treeConstruction(ptr,highestBit,bitBase,tempNums);
            int result=-1;
            findEle(ptr->left,ptr->right,result);  // ptr is guaranteed to have two children
            // we do not delete the tree
            return result;
        }
        void findEle(bitTreeNode *left, bitTreeNode *right, int &result)
        {
            if ((left==0)||(right==0))
            {
                result = -1;
                return;
            }
            int temp=-1; result = -1;
            if ((left->nums>=0)&&(right->nums>=0))
                result = (left->nums) ^ (right->nums);
            else if ((left->nums<0)&&(right->nums<0))
            {
                findEle(left->left,right->right,temp);
                if (temp>result)
                    result = temp;
                findEle(left->right,right->left,temp);
                if (temp>result)
                    result = temp;
                if (result>0)
                    return;
                findEle(left->right,right->right,temp);
                if (temp>result)
                    result = temp;
                findEle(left->left,right->left,temp);
                if (temp>result)
                    result = temp;
            }
            else if (left->nums<0)
            {
                findEle(left->left,right,temp);
                if (temp>result)
                    result = temp;
                findEle(left->right,right,temp);
                if (temp>result)
                    result = temp;
            }
            else
            {
                findEle(left,right->left,temp);
                if (temp>result)
                    result = temp;
                findEle(left,right->right,temp);
                if (temp>result)
                    result = temp;
            }
        }
        void treeConstruction(bitTreeNode* &ptr, int startBit, vector<int> &bitBase, vector<int> &tempNums)
        {
            ptr->nums = -1;
            if (tempNums.size()==1)
            {
                ptr->nums = tempNums[0];
                ptr->left = ptr->right = 0;
                return;
            }
            if (startBit==0)
                return;
            ptr->left = new bitTreeNode;
            ptr->right = new bitTreeNode;
            vector<int> leftPart, rightPart;
            for (int i=0; i<tempNums.size(); i++)
            {
                if ((tempNums[i]&bitBase[startBit-1])==0)
                    leftPart.push_back(tempNums[i]);
                else
                    rightPart.push_back(tempNums[i]);
            }
            tempNums.erase(tempNums.begin(),tempNums.end());
            if (leftPart.size()==0)
            {
                delete ptr->left;
                ptr->left = 0;
            }
            else
                treeConstruction(ptr->left, startBit-1, bitBase, leftPart);
            if (rightPart.size()==0)
            {
                delete ptr->right;
                ptr->right = 0;
            }
            else
                treeConstruction(ptr->right, startBit-1, bitBase, rightPart);
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.