[Swift]LeetCode321. 拼接最大数 | Create Maximum Number

发布时间：2020-12-14 05:06:21 所属栏目：百科来源：网络整理

导读：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 ar

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 = 
nums2 = 
k = 
Output:
[3,4,6,5][9,1,2,5,8,3]5[9,3]

Example 2:

Input:
nums1 = 
nums2 = 
k = 
Output:
[6,7][6,4]5[6,7,4]

Example 3:

Input:
nums1 = 
nums2 = 
k = 
Output:
[3,9][8,9]3[9,9]

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

示例?1:

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

示例 2:

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

示例 3:

输入:
nums1 = 
nums2 = 
k = 
输出:
[3,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 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!