321. Create Maximum Number

Problem Link

Tutorial

The dynamic programming solution is rather straight forward. The greedy solution is like this. We enumerate how many digits we pick from each array. Each time we get the optimal respectively from two arrays, then merge them together. It is not possible that the overall optimal solution is from sub-optimal solutions for the two arrays. So this solution is valid. Then, the problem is how to select a optimal subarray of a certain length from the array and how to merge two arrays. Please see the code for details.

Solution

class Solution {
    int n, m;
    public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int> ret = vector<int> (k);
        fill(ret.begin(), ret.end(), 0);
        n = nums1.size();
        m = nums2.size();
        for (int i = 0; i <= k; i++) {
            if (n < i || m < k - i) {
                continue;
            }
            vector<int> a = select(nums1, i);
            vector<int> b = select(nums2, k - i);
            vector<int> c = merge(a, b);
            if (lexicographical_compare(ret.begin(), ret.end(), c.begin(), c.end()))
                ret = c;
        }
        return ret;
    }

    vector<int> merge(vector<int> &a, vector<int> &b) {
        auto qa = deque<int> (a.begin(), a.end());
        auto qb = deque<int> (b.begin(), b.end());
        auto ret = vector<int> ();
        while (!(qa.empty() && qb.empty())) {
            if (lexicographical_compare(qa.begin(), qa.end(), qb.begin(), qb.end())) {
                ret.push_back(qb.front());
                qb.pop_front();
            } else {
                ret.push_back(qa.front());
                qa.pop_front();
            }
        }
        return ret;
    }

    vector<int> select(vector<int> &nums, int k) {
        vector<int> ret = vector<int> ();
        for (int i = 0; i < nums.size(); i++) {
            while (ret.size() > 0 && ret[ret.size() - 1] < nums[i] && k - ret.size() <= nums.size() - 1 - i)
                ret.pop_back();
            if (ret.size() < k)
                ret.push_back(nums[i]);
        }
        return ret;
    }
};