leetcode Create Maximum Number - 细语呢喃

leetcode Create Maximum Number - 细语呢喃

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]

题目地址：leetcode Create Maximum Number

题意：

给定两个长度为m和n的数组，他们由0~9的数组组成，现在，让你通过这两个数组中的数字组建一个长度为k 的数组（k<=m+n) ,原来数组的相对顺序要保留。

思路：

递归写法TLE了。

问了一下CJL的思路~其实都差不多。我是直接原串找当前符合条件的最大的值，然后递归，他是枚举长度，然后找符合长度的。。。

第7个AC~哈哈~

我A这题的时候。。。这题一共 7个AC，410+次提交。。。通过率1%…  难度medium，现在改成hard了。。。

枚举第一个数组A的个数i，那么数组B的个数就确定了 k -i。

然后枚举出A和B长度分别为i和k-i的最大子数组，（可以用栈，类似leetcode Remove Duplicate Letters）

最后组合看看哪个大。

组合的过程类似合并排序，看看哪个数组大，就选哪个。

枚举数组长度复杂度O(k)，找出最大子数组O(n)，合并的话O(k^2)

而k最坏是m+n,所以总的复杂度就是O((m+n)^3)

Read full article from leetcode Create Maximum Number - 细语呢喃