Strictly O(NK) C++ Solution with detailed explanation


  • 4
    S
    class list1
    {
        vector<int> a;
        vector<vector<int>> f;
    public:
        list1() = delete;
        inline int size() {return a.size();}
        inline int next(int x,int d) {return f[x][d];}
        list1(vector<int>& a0)
        {
            a = a0;
            f = vector<vector<int>>(a0.size() + 1,vector<int>(10,INT_MAX));
            for (int i = 0;i<a0.size();i++)
            {
                f[i][a[i]] = i;
                for (int j = i-1;j>=0;j--)
                {
                    if (a[j] == a[i]) break;
                    f[j][a[i]] = i;
                }
            }
        }
    };
    
    //dmd for detect_max_digit
    // dmd(a,x,rem) -> (max_digit, pos) , where a[pos-1] == max_digit
    // list a , from x, need rem numbers, x not included.
        
    pair<int,int> dmd(list1& a,int x,int rem)
    {
        for (int d = 9;d >= 0;d--)
        {
            int pos = a.next(x,d);
            if (pos == INT_MAX) continue;
            if (a.size() - (pos + 1) >= rem)
            return make_pair(d,pos + 1);
        }
    }
    
    
    class Solution {
    public:
        vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
            list1 a1 = list1(nums1);
            int N1 = nums1.size();
            list1 a2 = list1(nums2);
            int N2 = nums2.size();
            
            auto ret = vector<int>(k,0);
            auto f = vector<int>(N1 + 1,0); 
            //f[i] denote a1[0..i-1] need a2[0..f[i]-1] to reach the current maximal number, and can expand to length k
            // in other words, the state is : the number is current maximal and can be expanded, list1 begin with a1[i] and list2 with a2[f[i]] 
            for (int d = 1;d <= k;d++)
            {
                int maxDigit = -1;
                auto tmpf = vector<int>(N1 + 1,INT_MAX);
                for (int x = 0;x<=N1;x++)
                {
                    int y = f[x];
                    if (y == INT_MAX) continue;
                    auto m1 = dmd(a1,x,k-d-(N2-y)); 
                    auto m2 = dmd(a2,y,k-d-(N1-x));
                    maxDigit = max(maxDigit,m1.first);
                    maxDigit = max(maxDigit,m2.first);
                }
                ret[d-1] = maxDigit;
                for (int x = 0;x<=N1;x++)
                {
                    int y = f[x];
                    if (y == INT_MAX) continue;
                    auto m1 = dmd(a1,x,k-d-(N2-y));
                    if (m1.first == maxDigit)
                    tmpf[m1.second] = min(tmpf[m1.second],y);
                    auto m2 = dmd(a2,y,k-d-(N1-x));
                    if (m2.first == maxDigit)
                    tmpf[x] = min(tmpf[x],m2.second);
                }
                f = tmpf;
            }
            return ret;
        }
    };
    

    Any Question is welcome and will be answered as soon as possible.
    Detailed explanation is coming soon!
    You may firstly read my code, it's quite easy to understand.

    Detailed Solution

    Let a1,a2 be the two list from where we construct the maximal number.
    Let N1,N2 denote the size of a1,a2.
    We construct the maximal number digit by digit.

    Suppose we are constructing the d-th digit(ret[0..d-1] is done) and we have a set of states S = {(a1,b1),(a2,b2),...(a_N,b_N)},For each state (x,y) in S, it means we use a1[0..(x-1)] and a2[0..(y-1)] to construct ret[0..d-1] and a1[x..N1] and a2[y..N2] are avaliabe to construct the remaining digits.

    In the iteration, we need to construct the d-th digit as well as the set S', that is from where we can construct the d+1-th digit.

    For every state (x,y) in S, we use the function "dmd" to obtain the biggest d-th digit we can get from it.
    Let maxdigit = {max(dmd(x,y)[1])|(x,y) in S}, it is the d-th digit.

    As we now the d-th digit,
    We scan S again,
    For every state (x,y) in S, we use the function "dmd" to obtain the (x',y) and (x,y') it extands to,
    if a1[x'-1] == maxdigit, we add (x',y) to S'.
    if a2[y'-1] == maxdigit, we add (x,y') to S'.

    Now we can construct the d+1-th digit from S', note that the size of S' is at most N1, for(x,y1) and (x,y2), y1 < y2, (x,y2) is needless to be recorded.

    Finally I'd like to use an typical example to illustrate the process.

    a1 = [8,1] a2 = [8,9] k = 4

    S = {(0,0)}

    the first digit is 8,

    S' = {(0,1),(1,0)}

    the second digit is 9, we construct it from (0,1)

    S'' = {(0,2)}

    the remain digits are 8 and 1,
    we finally reach 8981.


  • 0
    L

    when a1 = [8,7] a2 = [8,9,1] k = 4, the first digit should be 9 to get 9187


  • 0
    S

    You are quite right, maybe k = 5 is better.


  • 0
    Z

    Could you plz explain this case: [1,5], [8,2,3]. when k=4, the number is 8523, when k=5, the number is 82315, you can't generate 82315 from the states of 8523 right?


  • 0
    S

    Actually, the strategies differs when k is modified. When k = 5, state 8523 is illegal, I wonder if you are satisfied with this answer.


  • 0

    This is absolutely awesome. In fact, this was my very first idea, but I failed to notice that the number of states is limited and they tend to become duplicates of each other, so I just kept doubling them and the whole thing was O(2^k), which was of course very bad both CPU and memory-wise.


  • 0
    S

    Thank you for your patience and the up vote! XD


  • 0
    M

    Seems this is O(KN^2)? The function "dmd" is O(N).


  • 0
    S

    It iterates at most 9 times, in my opinion..


  • 0
    M

    The function call a.next(x,d) is O(N).


  • 0
    S
    This post is deleted!

  • 0
    S

    I think the function next(x,d) is O(1), it just returns f[x][d].


  • 0
    M

    Oh you're right!


  • 0
    E

    Very strange.... Run that in visula studio 2015 and that works incorrectly while on leetcode all unit tests are passed. Whta is wrong with running that?


  • 0
    S

    I suggest you running the same test case online and in your IDE, if there exists any discrepancy, please show me, thank you.


  • 0
    E

    Yes, there is descrpancy even for the most basic unit test maxNumber(std::vector<int>{ 3, 4, 6, 5 }, std::vector<int> { 9, 1, 2, 5, 8, 3 }, 5);

    I suspect this happens because dmd(list1& a,int x,int rem) doesn't always return a value


  • 0
    S

    I guess it will always return a value, for you enter the function in a legal state, which means in the worst case you can choose all the remaining digits to form a number long enough.


  • 0
    X

    can you explain what is list1 for?

    thanks.


  • 0
    S

    I guess you know Chinese.
    为了在O(1)时间算next[x][d], 从x开始第一个d在哪


  • 0
    C

    Awsome! Thanks for your sharing!


Log in to reply
 

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