A 24 ms C++ solution with comments


  • 0
    L

    // Get the max number from an array.
    void getMax(int* num, // array. Should have capacity >= len
    int len, // array length
    int* result, // buffer for getting back the result. Should have capacity >= t
    int t) // number of digit of the max number. t <= len.
    {
    int n;
    int top = 0; // Take the result as a stack and this is the top index of the stack.

        // Fill the first element
        result[0] = num[0];
        
        for(int i = 1; i < len; ++i)
        {
            n = num[i];
            // If top >= 0 AND result[top] is smaller than n AND there is enough remaining numbers to fill the result
            while(top >= 0 && result[top] < n && (t - top) <= (len - i) )
            {
                // Pop the top element.
                top--;
            }
            
            // Move to the new top
            top++;
            if(top < t)
                result[top] = n;
            else
               top = t - 1;  // stay at the last element.
        }
    }
    
    // Merge two numbers so they generate the max number.  This merge runs in linear time O(m + n)
    void merge(int* num1,    // num1 with length of len1
               int len1, 
               int* num2,    // num2 with length of len2
               int len2, 
               int* result)  // result with length of (len1 + len2)
    {
        int i;
        int j, k;
        int t = len1 + len2;
        for(i = 0, j = 0, k = 0; i < t; ++i)
        {
            if(j < len1 && k < len2)
            {
                // Pick the larger number
                if(num1[j] > num2[k])
                    result[i] = num1[j++];
                else if(num1[j] < num2[k])
                    result[i] = num2[k++];
                else // if equal
                {
                    int remaining1 = len1 - j;
                    int remaining2 = len2 - k;
                    if(remaining1 > remaining2)
                    {
                        // Compare remaining part.  Pick the larger one.
                        if(memcmp(num1 + j, num2 + k, sizeof(int) * remaining2) >= 0)
                            result[i] = num1[j++];
                        else
                            result[i] = num2[k++];
                    }
                    else
                    {
                        if(memcmp(num2 + k, num1 + j, sizeof(int) * remaining1) >= 0)
                            result[i] = num2[k++];
                        else
                            result[i] = num1[j++];
                    }
                }
            }
            else if(j < len1 && k >= len2)
            {
                // Keep adding the remaining numbers
                result[i] = num1[j++];
            }
            else // if(j >= len1 && k < len2)
            {
                // Keep adding the remaining numbers
                result[i] = num2[k++];
            }
        }
    }
    
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        
        // Allocate memory
        int* num = new int[k * 4];
        int* buf1 = num + k;
        int* buf2 = num + k * 2;
        int* temp = num + k * 3;
        int memSize = sizeof(int) * k;
        memset(num, 0, memSize);
        
        int i;
        int t1, t2;
        int len1 = nums1.size();
        int len2 = nums2.size();
        if(len1 == 0 && len2 > 0)
        {
            getMax(&nums2[0], len2, num, k);
        }
        else if(len1 > 0 && len2 == 0)
        {
            getMax(&nums1[0], len1, num, k);
        }
        else if(len1 > 0 && len2 > 0)
        {
            if(len1 <= len2)
            {
                int smaller = len1 < k ? len1 : k;
                for(i = k - len2; i <= smaller; ++i)
                {
                    // Tranverse the numbers with all possible combinations
                    t1 = i;
                    t2 = k - i;
                    getMax(&nums1[0], len1, buf1, t1);
                    getMax(&nums2[0], len2, buf2, t2);
                    merge(buf1, t1, buf2, t2, temp);
                    if(memcmp(num, temp, memSize) < 0)
                        memcpy(num, temp, memSize);
                }
            }
            else
            {
                int smaller = len2 < k ? len2 : k;
                for(i = k - len1; i <= smaller; ++i)
                {
                    // Tranverse the numbers with all possible combinations
                    t2 = i;
                    t1 = k - i;
                    getMax(&nums1[0], len1, buf1, t1);
                    getMax(&nums2[0], len2, buf2, t2);
                    merge(buf1, t1, buf2, t2, temp);
                    if(memcmp(num, temp, memSize) < 0)
                        memcpy(num, temp, memSize);
                }
            }
        }
        
        vector<int> rev(num, num + k);
        delete [] num;
        
        return rev;
    
    }

  • 0

    You'd better modify your code further to make it look nice and able to read, thanks in advance!


Log in to reply
 

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