leetcode

321. Create Maximum Number

fightingminionLeave a comment

Difficulty: Hard

Frequency: N/A

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]

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        int n = nums1.size(), m = nums2.size();
        vector<int> result;
        for (int i = max(0, k - m); i <= k && i <= n; i++) {
            vector<int> tmp = merge(maxArray(nums1, i), maxArray(nums2, k - i), k);
            if (greater(tmp, 0, result, 0)) result = tmp;
        }
        return result;
    }
    vector<int> merge(vector<int> nums1, vector<int> nums2, int k) {
        vector<int> result;
        for (int i = 0, j = 0, r = 0; r < k; r++) {
            if (greater(nums1, i, nums2, j)) result.push_back(nums1[i++]);
            else result.push_back(nums2[j++]);
        }
        return result;
    }
    bool greater(vector<int> nums1, int i, vector<int> nums2, int j) {
        while (i < nums1.size() && j < nums2.size() && nums1[i] == nums2[j]) {
            i++;
            j++;
        }
        return j == nums2.size() || i < nums1.size() && nums1[i] > nums2[j];
    }
    vector<int> maxArray(vector<int> nums, int k) {
        int n = nums.size();
        vector<int> result(k, 0);
        for (int i = 0, j = 0; i < n; i++) {
            while (n - i + j > k && j > 0 && result[j - 1] < nums[i]) j--;
            if (j < k) result[j++] = nums[i];
        }
        return result;
    }
};

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

 

Things to learn:

Leave a comment