• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode321.拼接最大数|CreateMaximumNumber

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:https://www.cnblogs.com/strengthen/p/10260640.html 
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

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]

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

示例 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]

380 ms

 1 class Solution {
 2     func maxNumber(_ nums1: [Int], _ nums2: [Int], _ k: Int) -> [Int] {
 3         let m = nums1.count
 4         let n = nums2.count
 5         
 6         var res = [Int]()
 7         
 8         let c = max(0, k-n)
 9         
10         for i in c...min(k, m) {
11             let r1 = maxNumArr(nums1, i)
12             let r2 = maxNumArr(nums2, k-i)
13             let tmp = maxNums(r1, r2, k)
14             if isGreater(tmp, res, 0, 0) {
15                 res = tmp
16             }
17         }
18         
19         return res
20     }
21     
22     func maxNumArr(_ nums : [Int], _ k : Int) -> [Int] {
23         var res = [Int]()
24         for i in 0..<nums.count {
25             let num = nums[i]
26             while !res.isEmpty && num > res.last! && nums.count + res.count > k + i {
27                 res.removeLast()
28             }
29             res.append(num)
30             continue
31         }
32         return res
33     }
34     
35     func maxNums(_ num1 : [Int], _ num2 : [Int],_ k : Int) -> [Int] {
36         var res = [Int]()
37         var i = 0 , j = 0
38         for _ in 0..<k {
39             if isGreater(num1, num2, i, j) {
40                 res.append(num1[i])
41                 i+=1
42             }else {
43                 res.append(num2[j])
44                 j+=1
45             }
46         }
47         
48         return res
49     }
50     
51     func isGreater(_ nums1: [Int], _ nums2 : [Int], _ i : Int, _ j : Int) -> Bool {
52         var i = i , j = j
53         while i < nums1.count , j < nums2.count && nums1[i] == nums2[j] {
54             i+=1
55             j+=1
56         }
57         
58         return j == nums2.count || (i < nums1.count && nums1[i] > nums2[j])
59     }
60 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
swift2.0语法可选类型发布时间:2022-07-13
下一篇:
JS&amp;Swift相互交互发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap