【题目描述】
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
Given nums1 = [3, 4, 6, 5], nums2 = [9, 1, 2, 5, 8, 3], k = 5
return [9, 8, 6, 5, 3]
Given nums1 = [6, 7], nums2 = [6, 0, 4], k = 5
return [6, 7, 6, 0, 4]
Given nums1 = [3, 9], nums2 = [8, 9], k = 3
return [9, 8, 9]
给出两个长度分别是m和n的数组来表示两个大整数，数组的每个元素都是数字0-9。从这两个数组当中选出k个数字来创建一个最大数，其中k满足k <= m + n。选出来的数字在创建的最大数里面的位置必须和在原数组内的相对位置一致。返回k个数的数组。你应该尽可能的去优化算法的时间复杂度和空间复杂度。
样例
给出 nums1 = [3, 4, 6, 5], nums2 = [9, 1, 2, 5, 8, 3], k = 5
返回 [9, 8, 6, 5, 3]
给出 nums1 = [6, 7], nums2 = [6, 0, 4], k = 5
返回 [6, 7, 6, 0, 4]
给出 nums1 = [3, 9], nums2 = [8, 9], k = 3
返回 [9, 8, 9]
【题目链接】
www.lintcode.com/en/problem/create-maximum-number/
【题目解析】
从nums1中选择i个数，从nums2中选择k-i个数，使得合成的数最大。
分成两个子问题：
1. 如何从一个数组中选择i个数，使这i个数表示的数值是所有候选中最大的
比如[9, 1, 2, 5, 8, 3] i = 2; 如何得到 [9,8]
2. 如何合并两个数组使得形成最大的值
比如[9, 8, 3] [6,5]; 如何得到[9,8,6,5,3]
【参考答案】
网友评论