拼接最大数

目录

一、题目内容

二、解题思路

三、代码

---

一、题目内容

给定长度分别为 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]

二、解题思路

题目太难，总之就是遍历所有的组合k=i+j，然后融合两个数组，比较每次res的大小，得到最大的。

三、代码

class Solution1:
    def maxNumber(self, nums1: list, nums2: list, k: int) -> list:
        m = len(nums1)
        n = len(nums2)

        res = [0 for _ in range(k)]
        for i in range(max(0, k - n), k + 1):
            if i <= m:
                arr = self.merge(nums1=self.maxlist(nums1, i),
                                 nums2=self.maxlist(nums2, k - i),
                                 k=k)
                if self.compare_same_location_num(arr, 0, res, 0):
                    res = arr
        return res

    def maxlist(self, nums, k):
        n = len(nums)
        res = [0 for _ in range(k)]
        j = 0
        for i in range(n):
            while n - i + j > k and j > 0 and nums[i] > res[j - 1]:
                j -= 1
            if j < k:
                res[j] = nums[i]
                j += 1
        return res

    def merge(self, nums1, nums2, k):
        res = [0 for _ in range(k)]
        i, j = 0, 0
        for r in range(k):
            if self.compare_same_location_num(nums1, i, nums2, j):
                res[r] = nums1[i]
                i += 1
            else:
                res[r] = nums2[j]
                j += 1
        return res

    def compare_same_location_num(self, nums1, i, nums2, j):
        while i < len(nums1) and j < len(nums2) and nums1[i] == nums2[j]:
            i += 1
            j += 1
        return j == len(nums2) or (i < len(nums1) and nums1[i] > nums2[j])


class Solution2:
    def maxNumber(self, nums1: list, nums2: list, k: int) -> list:

        # 求出单个数组可以组成i位的最大数组
        def getMaXArr(nums, i):
            if not i:
                return []
            # pop表示最多可以不要nums里几个数字，要不组成不了i位数字
            stack, pop = [], len(nums) - i
            for num in nums:
                while pop and stack and stack[-1] < num:
                    pop -= 1
                    stack.pop()
                stack.append(num)
            return stack[:i]

        def merge(tmp1, tmp2):
            return [max(tmp1, tmp2).pop(0) for _ in range(k)]

        res = [0] * k
        for i in range(k + 1):
            if i <= len(nums1) and k - i <= len(nums2):
                # 取num1的i位, num2的k - i
                tmp1 = getMaXArr(nums1, i)
                tmp2 = getMaXArr(nums2, k - i)
                # 合并
                tmp = merge(tmp1, tmp2)
                if res < tmp:
                    res = tmp
        return res

if __name__ == '__main__':
    nums1 = [3, 4, 6, 5]
    nums2 = [9, 1, 2, 5, 8, 3]
    k = 5

    s1 = Solution1()
    ans1 = s1.maxNumber(nums1, nums2, k)
    print(ans1)

    s2 = Solution2()
    ans2 = s2.maxNumber(nums1, nums2, k)
    print(ans2)

本文地址：https://blog.csdn.net/qq_36556893/article/details/110470551