0321：拼接最大数（★★）

2015-11-17 约 703 字预计阅读 2 分钟次阅读

力扣第 321 题

题目

给你两个整数数组 nums1 和 nums2，它们的长度分别为 m 和 n。数组 nums1 和 nums2 分别代表两个数各位上的数字。同时你也会得到一个整数 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]

提示：

m == nums1.length
n == nums2.length
1 <= m, n <= 500
0 <= nums1[i], nums2[i] <= 9
1 <= k <= m + n

相似问题：

分析

假设 nums1 删除 i 个，nums2 删除 m+n-k-i 个
删除 i 个得到的序列最大，即是问题 0402
归并求出剩下 k 个数能拼成的最大数
- 为了方便，归并时直接比较整个数组

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        def gen(A,i):
            sk = []
            for c in A:
                while i and sk and sk[-1]<c:
                    sk.pop()
                    i -= 1
                sk.append(c)
            return sk[:-i] if i else sk

        m,n = len(nums1),len(nums2)
        res = [0]*k
        for i in range(min(m,m+n-k)+1):
            A = gen(nums1,i)
            B = gen(nums2,m+n-k-i)
            res = max(res,[max(A,B).pop(0) for _ in range(k)])
        return res

165 ms

*附加

还有种依次选择每一位的贪心方法
先看第一位，为了尽可能大，先考虑选 9
- 找到 nums1 第一个 9 的下标 i
  - 剩下的数在 nums1[i+1:] 和 nums2 中选
  - 如果够选，这即是一个最佳候选，可记为 <i+1,0>
- 同理在 nums2 中看是否有一个最佳候选 <0,j+1>
- 只要存在最佳候选，第一位便确定为 9，同时所有最佳候选参与下一轮
若 9 不可能，就继续考虑 8，依此类推
依此循环，选出 k 位即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        m,n = len(nums1),len(nums2)
        A1,A2 = ([[] for _ in range(10)] for _ in range(2))
        for i,x in enumerate(nums1):
            A1[x].append(i)
        for i,x in enumerate(nums2):
            A2[x].append(i)
        res = []
        Q = {(0,0)}
        for _ in range(k):
            for x in range(9,-1,-1):
                tmp = set()
                B1,B2 = A1[x],A2[x]
                for i,j in Q:
                    p1 = bisect_left(B1,i)
                    if p1<len(B1) and m-B1[p1]+n-j+len(res)>=k:
                        tmp.add((B1[p1]+1,j))
                    p2 = bisect_left(B2,j)
                    if p2<len(B2) and m-i+n-B2[p2]+len(res)>=k:
                        tmp.add((i,B2[p2]+1))
                if tmp:
                    Q = tmp
                    res.append(x)
                    break
        return res

73 ms

目录

0321：拼接最大数（★★）

题目

分析

解答

*附加