LeetCode 321. Create Maximum Number

简介: 给定长度分别为 m 和 n 的两个数组,其元素由 0-9 构成,表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数,要求从同一个数组中取出的数字保持其在原数组中的相对顺序。求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。

v2-eb15b7410d583e3dff813c466c101a9b_1440w.jpg

Description



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.


Note: You should try to optimize your time and space complexity.


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]


描述



给定长度分别为 m 和 n 的两个数组,其元素由 0-9 构成,表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数,要求从同一个数组中取出的数字保持其在原数组中的相对顺序。


求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。


说明: 请尽可能地优化你算法的时间和空间复杂度。


示例 1:


输入:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
输出:
[9, 8, 6, 5, 3]


示例 2:


输入:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
输出:
[6, 7, 6, 0, 4]


示例 3:


输入:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
输出:
[9, 8, 9]


思路



  • 子问题 1 :对于一个给定的无序整数数组,从其中找出 k 个数构成一个新的整数,k 个数之间的相对位置不变,使得新构成的整数的值最大。我们借助栈来实现,我们即给的给定的数组的元素为 n,需要的取出的元素个数为 k,剩下的元素个数为 t = n - k,我们不断的遍历数组中的元素,如果当前元素比栈顶的元素大,并且此时剩下的可以被踢掉的元素个数 t 大于零,我们弹出栈顶元素;否则我们将当前元素压入栈顶。
  • 子问题 2 :给定两个数组,从这两个数组中交替的选数字出来,只能从前往后选,构成一个新数组,使得这个数组最大。「数组大小的比较:依次标胶每一个元素,遇到第一数大的数组大」。用两个队列来实现,如果队列 1 大于队列 2,我们弹出队列 1 的元素到结果数组中,否则弹出队列 2 的元素,直到所有的元素都被取完。
  • 本题:我们从第一个数组中取 i 个元素找到一个最数组,从第二个数组中取出 k - i 个数构成最大数组,将两个数组合并构成新的数组,在所有的新的数组中我们取最大的数组。


# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-02-24 14:35:27
# @Last Modified by:   何睿
# @Last Modified time: 2019-02-26 16:08:04
from collections import deque
class Solution:
    def maxNumber(self, nums1: [int], nums2: [int], k: int) -> [int]:
        ans = []
        for i in range(k + 1):
            # 如果已经超出了第一个数组的范围,循环结束
            if i > len(nums1): break
            # 如果 k - i 比第二个数组的元素个数更多,
            # 说明第二个数组不能够提供足够的元素,继续循环
            if k - i > len(nums2): continue
            # 产生新的组合
            newans = self._merge(self._Max(nums1, i), self._Max(nums2, k - i))
            # 取最大的组合
            ans = max(ans, newans)
        return ans
    def _Max(self, nums, k):
        # 需要去掉的个数
        drop = len(nums) - k
        stack = []
        # 遍历每一个元素
        for num in nums:
            # 如果栈不为空 并且 drop 大于零 并且 num 大于栈顶元素
            while stack and drop > 0 and num > stack[-1]:
                # 弹出栈顶元素
                stack.pop()
                # 需要弹出的元素个数减一
                drop -= 1
            stack.append(num)
        # 返回前 k 个元素
        return stack[:k]
    def _merge(self, num1, nums2):
        # 将列表转换成队列
        queue1 = deque(num1)
        queue2 = deque(nums2)
        res = []
        while queue1 and queue2:
            # 队列大小的比较
            # 对队列每个元素从前向后比较,只要有一个比较大,则该队列比较大
            if queue1 > queue2: res.append(queue1.popleft())
            else: res.append(queue2.popleft())
        # 添加队列剩下的元素
        if queue1: res += queue1
        if queue2: res += queue2
        return res


源代码文件在 这里

目录
相关文章
|
算法
Leetcode 313. Super Ugly Number
题目翻译成中文是『超级丑数』,啥叫丑数?丑数就是素因子只有2,3,5的数,7 14 21不是丑数,因为他们都有7这个素数。 这里的超级丑数只是对丑数的一个扩展,超级丑数的素因子不再仅限于2 3 5,而是由题目给定一个素数数组。与朴素丑数算法相比,只是将素因子变了而已,解法还是和朴素丑数一致的。
98 1
|
5月前
|
存储 SQL 算法
LeetCode 题目 65:有效数字(Valid Number)【python】
LeetCode 题目 65:有效数字(Valid Number)【python】
|
6月前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
42 0
|
存储
Leetcode Single Number II (面试题推荐)
给你一个整数数组,每个元素出现了三次,但只有一个元素出现了一次,让你找出这个数,要求线性的时间复杂度,不使用额外空间。
38 0
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
LeetCode 136. 只出现一次的数字 Single Number
LeetCode 136. 只出现一次的数字 Single Number
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
52 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
102 2