O((m+n)*k*k) algorithm with DP and greedy


  • 0
    H

    This is a very challenging problem.

    The first step is to use dp solution find the num[m, i], which means the max number with i digits from num[0]~num[m]. This part of DP is already a hard question, and many similar questions can be found (e.g.: Problem 72 or 115). The recursive equation is: dp(m,k) = max(dp(m-1, k), dp(m-1,k-1)+num[m]). But, here, since the backtrace is only 1 step ahead, we can save memory to be O(k) of less-than-k-digit numbers. We can use O(mk) time to run through the dp, and each max comparison will take another O(k) time to finish. Thus the overall the generation of maxNum(m, k) is O(mk*k). This piece of function is here:

    vector<vector<int>> maxNum(vector<int> & nums, int k) {
        vector<vector<int> > record(k+1);
        for (int i = 0; i < nums.size(); ++i) {
            for (int kk = k; kk >= 1; --kk) {
                if (kk>i) record[kk].clear();
                vector<int> temp = record[kk-1];
                temp.push_back(nums[i]);
                record[kk] = maxVector(record[kk], temp);
            }
        }
        return record;     
    }
    

    The rest will be a greedy algorithm. For each i in [0,k], we have maxNum(num1, i) and maxNum(num2, k-i). The maximized merged number can be easily generated by a greedy algorithm follow a lex order. The largest merged number will be the final solution. This piece of algorithm with known maxNum(num1, i) and maxNum(num2, k-i) from DP is only O(k*k).

    Thus the overall time complexity of algorithm is O((m+n)kk). The space complexity is O((m+n)*k).

    Here is the overall solution:

    vector<int> maxVector(vector<int> &a, vector<int> &b) {
        if (a.size() > b.size()) return a;
        else if (a.size() < b.size()) return b;
        else {
            for (int i = 0; i<a.size(); ++i) {
                if (a[i] > b[i]) return a;
                else if (a[i] < b[i]) return b;
            }
            return a;
        }
    }
    
    vector<vector<int>> maxNum(vector<int> & nums, int k) {
        vector<vector<int> > record(k+1);
        for (int i = 0; i < nums.size(); ++i) {
            for (int kk = k; kk >= 1; --kk) {
                if (kk>i) record[kk].clear();
                vector<int> temp = record[kk-1];
                temp.push_back(nums[i]);
                record[kk] = maxVector(record[kk], temp);
            }
        }
        return record;     
    }
    
    vector<int> maxMerge(vector<int> & a, vector<int> & b) {
        vector<int> res;
        int i = 0;
        int j = 0;
        while (i<a.size() || j<b.size()) {
            if (i == a.size()) res.push_back(b[j++]);
            else if (j == b.size()) res.push_back(a[i++]);
            else if (a[i]>b[j]) res.push_back(a[i++]);
            else if (a[i]<b[j]) res.push_back(b[j++]);
            else {
                int ii = i, jj = j;
                while (ii<a.size() && jj<b.size() && a[ii] == b[jj]) {ii++; jj++;}
                if (ii == a.size() && jj == b.size()) res.push_back(a[i++]);
                else if (ii == a.size() || a[ii] < b[jj]) res.push_back(b[j++]);
                else if (jj == b.size() || a[ii] > b[jj]) res.push_back(a[i++]);
            }
        }
        return res;
    }
    
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        if (nums1.size()+nums2.size() == k) return maxMerge(nums1, nums2);
        vector<vector<int> > range1 = maxNum(nums1, k);
        vector<vector<int> > range2 = maxNum(nums2, k);
    
        vector<int> maxResult;
        for (int n1 = 0; n1 <= k; ++n1) {
            int n2 = k-n1;
            vector<int> temp = maxMerge(range1[n1], range2[n2]);
            maxResult = maxVector(maxResult, temp);
        }
        return maxResult;
    }
    

    BTW, this piece of code passes all my local tests, but it always reports failure in a simple test case in the leetcode test environment.

    [5,0,2,1,0,1,0,3,9,1,2,8,0,9,8,1,4,7,3]
    [7,6,7,1,0,1,0,5,6,0,5,0]
    31
    

    I suspect the leetcode compiling system might have some bugs somewhere.


  • 0
    J

    Could we not use DP to solve this problem?


  • 0
    B

    sorry don't know how to delete the comment. I got it wrong.


  • 0
    L

    you should modify your maxmerge:
    else if (ii == a.size() || a[ii] < b[jj]) res.push_back(b[j++]);
    else if (jj == b.size() || a[ii] > b[jj]) res.push_back(a[i++]);
    }
    the vector subscript out of range


Log in to reply
 

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