Sharing my 440ms C++ solution


  • -1
    T
    class Solution {
    private:
        vector<int> maxVector(vector<int> nums, int k)
        {
            int i, n;
            while(nums.size()>k)
            {
                n = nums.size();
                for(i=0; i<n-1; i++)
                {
                    if(nums[i]<nums[i+1])
                    {
                        nums.erase(nums.begin()+i);
                        break;
                    }
                }
                if(i==n-1)
                    nums.pop_back();
            }
            return nums;
        }
        
        bool compare(vector<int>& nums1, int i, vector<int>& nums2, int j)
        {
            while(i<nums1.size() && j<nums2.size() && nums1[i] == nums2[j])
            {
                i++;
                j++;
            }
            if(j==nums2.size())
                return true;
            else if(i<nums1.size() && nums1[i]>nums2[j])
                return true;
            else 
                return false;
        }
        
        vector<int> merge(vector<int>& nums1, vector<int>& nums2)
        {
            int i=0, j=0;
            vector<int> result;
            int n1 = nums1.size();
            int n2 = nums2.size();
            while(i+j < n1+n2)
            {
                if(compare(nums1, i, nums2, j))
                {
                    result.push_back(nums1[i]);
                    i++;
                }
                else
                {
                    result.push_back(nums2[j]);
                    j++;
                }
            }
            return result;
        }
        
    public:
        vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
            int n1 = nums1.size();
            int n2 = nums2.size();
            int i;
            vector<int> result(k, 0);
            for(i=max(0,k-n2); i<=min(n1,k); i++)
            {
                vector<int> num1 = maxVector(nums1, i);
                vector<int> num2 = maxVector(nums2, k-i);
                vector<int> temp = merge(num1, num2);
                if(compare(temp, 0, result, 0))
                    result = temp;
            }
            
            return result;
        }
    };

Log in to reply
 

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