Question

Formatted question description: https://leetcode.ca/all/321.html

You are given two integer arrays nums1 and nums2 of lengths m and n respectively. nums1 and nums2 represent the digits of two numbers. You are also given an integer k.

Create the maximum number of length k <= m + n from digits of the two numbers. The relative order of the digits from the same array must be preserved.

Return an array of the k digits representing the answer.

Example 1:

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

Example 2:

Input: nums1 = [6,7], nums2 = [6,0,4], k = 5
Output: [6,7,6,0,4]

Example 3:

Input: nums1 = [3,9], nums2 = [8,9], k = 3
Output: [9,8,9]

Constraints:

m == nums1.length
n == nums2.length
1 <= m, n <= 500
0 <= nums1[i], nums2[i] <= 9
1 <= k <= m + n

Algorithm

This question gave us two arrays, where the numbers are unordered, and gave us a k value of k <= n1 + n2, and then picked out k numbers from the two arrays, the relative order between the numbers is not Change, find the largest number that can be composed. The difficulty of this question is Hard, and the blogger has never come up with a solution, so he can refer to the solution of the great online gods. Since the size of k is uncertain, there are three possibilities:

The first is when k is 0, no number is taken in the two arrays.

The second is when k is not greater than the length of any one of the arrays. In this case, it is possible to take numbers from only one array, or take some of both.

The third case is that k is greater than the length of any one of the arrays, and you need to take the numbers from the two arrays separately. As for how many from each array, you must consider each case, and then change the result each time.

In order to be able to handle these three situations at the same time, assuming that the number of i is taken from the array nums1, then the number of k-i needs to be taken from nums2. So how to determine the range of i? From the second case, if k is not greater than the length of any array, then it is possible to take only k from one of the arrays, that is to say, it is not necessary to take the number from nums1, so i can be as small as 0. If it is the third case, assuming that k is greater than the length of nums2, even if all the numbers in nums2 are taken out, there is no way to make up k. The extra k-n2 numbers must be taken from nums1. So just compare the size of 0 and k-n2, and take the larger one as the starting range of i. So how big i can be depends on the size of k and n1. If k is less than or equal to n1, then only k is required. If k is greater than n1, then only n1 can be selected from nums1. Take it from nums2.

Ok, now I know the situation of taking numbers from two arrays respectively. Here, I hope that the i numbers taken from nums1 are the largest combination. Similarly, the k-i numbers taken from nums2 are also the largest combination of numbers. How can we extract the largest combination? For example, the length of the current array is n, k numbers need to be taken out, and a variable drop = n-k is defined to indicate the number of numbers that need to be dropped. The numbers in the array are traversed and the following loop is performed. If drop is an integer at this time, and the result The length of the array is not 0, and the last element of the result array is less than the element currently traversed, then the last element of the result array is removed. At this time, drop is decremented by 1, and the loop is repeated until any of the above conditions are not met, and then the current element is added to the result array , And finally return the first k elements in the result array.

Now I have taken out the i largest combination numbers from nums1 and ki largest combination numbers from nums2. The last step is to mix and sort the two extracted arrays into an array, between the respective numbers in the small arrays The relative order remains unchanged. For a mixture of two arrays, compare the sizes of the two arrays (by element comparison), then take the first element from the current larger array, and then delete the head element until the next time and then compare again, until the two arrays are both Stop for nothing.

Code

import java.util.Arrays;

public class Create_Maximum_Number {

    public static void main(String[] args) {
        Create_Maximum_Number out = new Create_Maximum_Number();
        Solution s = out.new Solution();

        System.out.println(Arrays.toString(s.maxNumber(new int[]{3, 4, 6, 5}, new int[]{9, 1, 2, 5, 8, 3}, 5)));
    }

    // First find out the maximum number for each array,
    // and then merge it into a global maximal one.
    public class Solution {
        public int[] maxNumber(int[] nums1, int[] nums2, int k) {
            int[] result = new int[k];
            int n1 = nums1.length;
            int n2 = nums2.length;

            // similar idea to 3-d DP: start from 0 to k
            for (int i = Math.max(0, k - n2); i <= Math.min(n1, k); i++) {

                // step 1: find the largest number from each array, and merge into one
                int[] list1 = findMax(nums1, i);
                int[] list2 = findMax(nums2, k - i);

                // step 2: then merge into one
                int[] curr = merge(list1, list2); // possible overflow

                if (greater(curr, 0, result, 0)) {
                    result = curr;
                }
            }

            return result;
        }

        private int[] findMax(int[] nums, int k) {
            int[] result = new int[k];

            int n = nums.length;
            int resultPointer = 0;

            // {9, 1, 2, 5, 8, 3}, k=5
            for (int i = 0; i < n; i++) {
                // @note: current digits larger than k needed digits
                //          len(current count in result) + n-1 (left in original array)

                int dropNeeded = n - k - (i - resultPointer);
                while (resultPointer > 0 && dropNeeded > 0 && nums[i] > result[resultPointer - 1]) {
                    resultPointer--;
                }

                if (resultPointer < k) {
                    result[resultPointer] = nums[i];
                    resultPointer++;
                }
            }

            return result;
        }

        private int[] merge(int[] list1, int[] list2) {
            int n1 = list1.length;
            int n2 = list2.length;

            int[] result = new int[n1 + n2];

            int i = 0;
            int j = 0;
            int k = 0;

            while (k < n1 + n2) {
                if (greater(list1, i, list2, j)) {
                    result[k++] = list1[i++];
                } else {
                    result[k++] = list2[j++];
                }
            }

            return result;
        }

        private boolean greater(int[] list1, int startPos1, int[] list2, int startPos2) {
            int n1 = list1.length;
            int n2 = list2.length;

            while (startPos1 < n1 && startPos2 < n2 && list1[startPos1] == list2[startPos2]) {
                startPos1++;
                startPos2++;
            }

            if (startPos2 == n2) {
                return true;
            }

            if (startPos1 < n1 && list1[startPos1] > list2[startPos2]) {
                return true;
            }

            return false;
        }
    }
}

// OJ: https://leetcode.com/problems/create-maximum-number/
// Time: O(M * (M + N)^2)
// Space: O(M + N)
// Ref: https://discuss.leetcode.com/topic/32272/share-my-greedy-solution
class Solution {
    vector<int> maxSubarray(vector<int> &A, int k) {
        int N = A.size();
        vector<int> ans;
        for (int i = 0; i < N; ++i) {
            while (ans.size() && ans.back() < A[i] && k - ans.size() < N - i) ans.pop_back();
            if (ans.size() < k) ans.push_back(A[i]);
        }
        return ans;
    }
    bool greater(vector<int> &A, int i, vector<int> &B, int j) {
        for (; i < A.size() && j < B.size() && A[i] == B[j]; ++i, ++j);
        return j == B.size() || (i < A.size() && A[i] > B[j]);
    }
    vector<int> merge(vector<int> &A, vector<int> &B, int k) {
        vector<int> ans;
        for (int i = 0, j = 0, r = 0; r < k; ++r) {
            ans.push_back(greater(A, i, B, j) ? A[i++] : B[j++]);
        }
        return ans;
    }
public:
    vector<int> maxNumber(vector<int>& A, vector<int>& B, int k) {
        int M = A.size(), N = B.size();
        vector<int> ans;
        for (int i = max(0, k - N); i <= k && i <= M; ++i) {
            auto a = maxSubarray(A, i), b = maxSubarray(B, k - i), v = merge(a, b, k);
            if (greater(v, 0, ans, 0)) ans = v;
        }
        return ans;
    }
};

class Solution(object):
  def maxNumber(self, _nums1, _nums2, k):
    """
    :type nums1: List[int]
    :type nums2: List[int]
    :type k: int
    :rtype: List[int]
    """

    def getKDigits(num, k):
      drop = len(num) - k
      stack = []
      for c in num:
        while drop > 0 and stack and stack[-1] < c:
          stack.pop()
          drop -= 1
        stack.append(c)
      return stack[:k]

    def merge(nums1, nums2):
      ans = []
      i = j = 0
      while i < len(nums1) and j < len(nums2):
        if nums1[i:] > nums2[j:]:
          ans.append(nums1[i])
          i += 1
        else:
          ans.append(nums2[j])
          j += 1

      if i < len(nums1):
        ans += nums1[i:]
      if j < len(nums2):
        ans += nums2[j:]
      return ans

    ans = []
    for i in range(0, k + 1):
      if i <= len(_nums1) and k - i <= len(_nums2):
        n1 = getKDigits(_nums1, i)
        n2 = getKDigits(_nums2, k - i)
        if i == 2:
          print
          n1, n2
        ans.append(merge(n1, n2))
    return max(ans)

func maxNumber(nums1 []int, nums2 []int, k int) []int {
	m, n := len(nums1), len(nums2)
	l, r := max(0, k-n), min(k, m)
	f := func(nums []int, k int) []int {
		n := len(nums)
		stk := make([]int, k)
		top := -1
		remain := n - k
		for _, x := range nums {
			for top >= 0 && stk[top] < x && remain > 0 {
				top--
				remain--
			}
			if top+1 < k {
				top++
				stk[top] = x
			} else {
				remain--
			}
		}
		return stk
	}

	var compare func(nums1, nums2 []int, i, j int) bool
	compare = func(nums1, nums2 []int, i, j int) bool {
		if i >= len(nums1) {
			return false
		}
		if j >= len(nums2) {
			return true
		}
		if nums1[i] > nums2[j] {
			return true
		}
		if nums1[i] < nums2[j] {
			return false
		}
		return compare(nums1, nums2, i+1, j+1)
	}

	merge := func(nums1, nums2 []int) []int {
		m, n := len(nums1), len(nums2)
		ans := make([]int, m+n)
		i, j := 0, 0
		for k := range ans {
			if compare(nums1, nums2, i, j) {
				ans[k] = nums1[i]
				i++
			} else {
				ans[k] = nums2[j]
				j++
			}
		}
		return ans
	}

	ans := make([]int, k)
	for x := l; x <= r; x++ {
		arr1 := f(nums1, x)
		arr2 := f(nums2, k-x)
		arr := merge(arr1, arr2)
		if compare(arr, ans, 0, 0) {
			ans = arr
		}
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

function maxNumber(nums1: number[], nums2: number[], k: number): number[] {
    const m = nums1.length;
    const n = nums2.length;
    const l = Math.max(0, k - n);
    const r = Math.min(k, m);
    let ans: number[] = Array(k).fill(0);
    for (let x = l; x <= r; ++x) {
        const arr1 = f(nums1, x);
        const arr2 = f(nums2, k - x);
        const arr = merge(arr1, arr2);
        if (compare(arr, ans, 0, 0)) {
            ans = arr;
        }
    }
    return ans;
}

function f(nums: number[], k: number): number[] {
    const n = nums.length;
    const stk: number[] = Array(k).fill(0);
    let top = -1;
    let remain = n - k;
    for (const x of nums) {
        while (top >= 0 && stk[top] < x && remain > 0) {
            --top;
            --remain;
        }
        if (top + 1 < k) {
            stk[++top] = x;
        } else {
            --remain;
        }
    }
    return stk;
}

function compare(nums1: number[], nums2: number[], i: number, j: number): boolean {
    if (i >= nums1.length) {
        return false;
    }
    if (j >= nums2.length) {
        return true;
    }
    if (nums1[i] > nums2[j]) {
        return true;
    }
    if (nums1[i] < nums2[j]) {
        return false;
    }
    return compare(nums1, nums2, i + 1, j + 1);
}

function merge(nums1: number[], nums2: number[]): number[] {
    const m = nums1.length;
    const n = nums2.length;
    const ans: number[] = Array(m + n).fill(0);
    let i = 0;
    let j = 0;
    for (let k = 0; k < m + n; ++k) {
        if (compare(nums1, nums2, i, j)) {
            ans[k] = nums1[i++];
        } else {
            ans[k] = nums2[j++];
        }
    }
    return ans;
}

321 - Create Maximum Number

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions