Create Maximum Number

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.

Example 1: nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5 return [9, 8, 6, 5, 3]

Example 2: nums1 = [6, 7] nums2 = [6, 0, 4] k = 5 return [6, 7, 6, 0, 4]

Example 3: nums1 = [3, 9] nums2 = [8, 9] k = 3 return [9, 8, 9]

• 当merge时候后续数字两三个或者更多相等的时候如何处理
• 左边取i个，右边取k-i个

class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int> ret;

        for(int i=max(0,k-(int)nums2.size());i<=min(k,(int)nums1.size());i++)
        {
            vector<int> tmp=merge(gen(nums1,i),gen(nums2,k-i));

            if(ret.empty() || bigger(tmp,ret))
            ret=tmp;
        }
        return ret;
    }

    vector<int> gen(vector<int>& nums,int k)
    {
        int start=0;
        vector<int> ret;

        while(k)
        {
            int maxVal=nums[start];
            int idx=start;
            for(int i=start+1;i<=(nums.size()-k);i++)
            {
                if(nums[i]>maxVal)
                {
                    maxVal=nums[i];
                    idx=i;
                }
            }
            k--;
            start=idx+1;
            ret.push_back(maxVal);
        }
        return ret;
    }

    bool bigger(vector<int> &nums1,vector<int> &nums2)
    {
        for(int i=0;i<nums1.size();i++)
        {
            if(nums1[i]>nums2[i])return true;
            else if(nums1[i]<nums2[i])return false;
        }
        return false;
    }
    vector<int> merge(vector<int> nums1,vector<int> nums2)
    {
        int i=0,j=0;
        vector<int> ret;
        while(i<nums1.size() && j<nums2.size())
        {
            if(nums1[i]<nums2[j])ret.push_back(nums2[j++]);
            else if(nums1[i]>nums2[j]) ret.push_back(nums1[i++]);
            else
            {
                int ni=i+1,nj=j+1;
                while(ni<nums1.size() || nj<nums2.size())
                {
                     if (ni == nums1.size() || (nj != nums2.size() && nums2[nj]>nums1[ni]))
                    {
                        ret.push_back(nums2[j++]);break;
                    }
                    else if(nj==nums2.size() || nums2[nj]<nums1[ni])
                    {
                        ret.push_back(nums1[i++]);break;
                    }
                    else
                    {
                        ni++;nj++;
                    }
                }

                if(nums1.size()==ni && nj==nums2.size())
                    ret.push_back(nums2[j++]);
            }
        }

        ret.insert(ret.end(),nums1.begin()+i,nums1.end());
        ret.insert(ret.end(),nums2.begin()+j,nums2.end());

        return ret;
    }
};