[leetcode] 321. Create Maximum Number 解题报告 - 小榕流光的专栏 - 博客频道 - CSDN.NET

[leetcode] 321. Create Maximum Number 解题报告 - 小榕流光的专栏 - 博客频道 - CSDN.NET

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]




思路: 也是麻烦的一题. 思路是从nums1中取i个最大值,从nums2中取k-i个最大值, 然后枚举各个i,然后合并取比较大的. 但是在具体的实现中其实还是比较麻烦的.

首先从一个数组取i个大的值时, 我们要尽量保留其降序的序列, 除非剩余的元素个数不足我们要取的个数

然后是合并的时候, 如果两个元素的当前元素相等, 那么我们还要考虑其后序元素的大小.

代码如下:

Read full article from [leetcode] 321. Create Maximum Number 解题报告 - 小榕流光的专栏 - 博客频道 - CSDN.NET