欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

拼接最大数

程序员文章站 2022-06-27 18:06:49
目录一、题目内容二、解题思路三、代码一、题目内容给定长度分别为m和n的两个数组,其元素由0-9构成,表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n)个数字拼接成一个新的数,要求从同一个数组中取出的数字保持其在原数组中的相对顺序。求满足该条件的最大数。结果返回一个表示该最大数的长度为k的数组。说明: 请尽可能地优化你算法的时间和空间复杂度。示例1:输入:nums1 = [3, 4, 6, 5]nums2 =......

目录

一、题目内容

二、解题思路

三、代码


一、题目内容

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