C++ 136ms solution


  • 0
    A
    class Solution {
    public:
        vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
            
            vector<int> res;
            bool first = true;
            for (int i=0; i<=k; i++) {
                
                if (i > nums1.size() || k-i > nums2.size())
                    continue;
                
                // Find max number from nums1 of length i
                vector<int> maxNum1 = findMax(nums1, i);
    
                // Find max number from nums2 of length k-i
                vector<int> maxNum2 = findMax(nums2, k-i);
    
                // Interleave to find the global max number
                vector<int> candidate = interleave(maxNum1, maxNum2);
                
                if (first) {
                    res = candidate;
                    first = false;
                }
                else if (compare(res, 0, candidate, 0))
                    res = candidate;
            }
            return res;
        }
        vector<int> findMax(vector<int>& nums, int len) {
            vector<int> maxNum;
            int prev_pos = -1;
            int maxi;
            for (int i=0; i<len; i++) {
                maxi = -1;
                int limit = nums.size()-len+i;
                for (int j=prev_pos+1; j<=limit; j++) {
                    if (nums[j] > maxi) {
                        maxi = nums[j];
                        prev_pos = j;
                    }
                }
                maxNum.push_back(maxi);
            }
            return maxNum;
        }
        vector<int> interleave(vector<int>& maxNum1, vector<int>& maxNum2) {
            vector<int> res;
            int i1=0, i2=0;
            while (i1<maxNum1.size() || i2<maxNum2.size()) {
                if (compare(maxNum1, i1, maxNum2, i2)) {
                    res.push_back(maxNum2[i2++]);
                }
                else {
                    res.push_back(maxNum1[i1++]);
                }
            }
            return res;
        }
        // Returns true if the new vec (starting at position j) is better than the old vec (starting at position i)
        bool compare(vector<int>& old_vec, int i, vector<int>& new_vec, int j) {
            
            while (i < old_vec.size() && j < new_vec.size() && old_vec[i]==new_vec[j]) {
                i++;
                j++;
            }
            return i==old_vec.size() || (j!=new_vec.size() && old_vec[i] < new_vec[j]);
        }
    };

Log in to reply
 

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