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)

 

 

Idea:

To find the maximum ,we can enumerate how digits we should get from nums1 , we suppose it is i.

So ,  the digits from nums2 is K – i.

And we can use a stack to get the get maximum number(x digits) from one array.(just like leetcode Remove Duplicate Letters

OK, Once we choose two maximum subarray , we should combine it to the answer.

It is just like merger sort, but we should pay attention to the case: the two digital are equal.

we should find the digits behind it to judge which digital we should choose now.

In other words,we should judge which subarry is bigger than the other.

That’s all.

The algorithm is O((m+n)^3) in the worst case.

If you have any question or suggest, I am happy you can comment on my blog .

Thanks, merry christmas :)

 

Solution

Java 21ms

 

C++ 60ms

 

Python 636ms

 

 

 

 

只需要greater函数的解释

为什么只需要比较两个子序列大小呢?

来看看我写的比较早的版本,主要注意合并的时候。

最大子数组 res1 用x来遍历,res2用y来遍历。

对于相等的情况,往后找直到其中一个比另一个大,或者一个到了数组的长度

  • 对于都未到达数组长度的,哪个大选哪个
  • 若x1 <  res1.length  ,说明x2到达数组的长度了,选res1 ,因为要给后面的数更早出现的机会
    • [3,3,4]  [3,3] k = 5
    • 答案为[3,3,4,3,3]
    • 选择的过程中,因为第二个到末尾了,第一个还没到,显然4比较大,要给4早出现的机会。所以选res1
  • 否则选res2(可能是x2 <  res2.length 也可能是 x1 == res1.length && x2 == res2.length)

根据上面的,只要比较res1比res2未选的部分哪个大就选哪个即可。

所以,简写为:

至于greater函数,可以和updateAns函数合并成如下:

 

 

递归寻找最大子数组

java 150ms,递归寻找效率肯定不如用栈

 

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Create Maximum Number
本文地址:https://www.hrwhisper.me/leetcode-create-maximum-number/

您的支持将鼓励我继续创作!

Leetcode , , . permalink.

24 thoughts on “leetcode Create Maximum Number

  1. [3,3,4] [3,3] k = 5
    答案为[3,3,4,3,3]

    假如是 [3,3,2] [3,3]
    [3,3,2] [3,3] k = 5
    答案为[3,3,2,3,3] => 这个不是对的结果吧

  2. get_max_sub_array 可以不用每次都从空的stack开始找吧,如果你有了长度为m的max_sub_array,要得到长度为m – 1的,就只需要从长度为m的sub_array里去掉一个最小的。不过不影响时间复杂度。

    • 没太看懂,“就只需要从长度为m的sub_array里去掉一个最小的”
      如果说是长度为3的数组,如[3, 5, 2](这也是长度为3的max_sub_array) 2是最小的 然而长度为2的最大子数组是[5,2]而不是[3,5]
      或者你的意思为枚举所有的子数组然后比较,那也应该取最大的子数组才对啊。。 然后复杂度还是O(n^2) (每次枚举过程中要比较一次)

  3. get_max_sub_array 可以修改一下,比如要k个数,就从index 0 开始,只要下一个数比它大并且剩下的数字个数还够k-1个就替换。这样可以线性时间

    vector get_max_sub_array(const vector &nums, int k) {
    vector res(k,0);
    int n = nums.size();
    int init = -1;
    for (int i = 0; i init)
    {
    init = nums[i];
    if (n-i == k)
    {
    res.push_back(init);
    k–;
    init = -1;
    }
    }
    }
    return res;
    }

    • 你这样不对吧~ 1.上面的res(k,0)已经开了k个空间,下面又push_back,这样最后的长度会超过k。 2. (n-i == k) 的时候才加入res,那么就是最后的k个才会进去啊。 3.而且你没有大于替换的过程。 = =||| 其实我用stack就是线性的时间。。。

  4. Hi,请教一下greater这个函数。merge的时候如果是单个digit来比较是会有问题的,具体的是,在两个数组的digit相等时会有问题。但是你提出的greater函数又是怎么保证解决这个问题的?

Leave a Reply

Your email address will not be published. Required fields are marked *