[Swift]LeetCode321. 拼接最大数 | Create Maximum Number_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

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 = tmp16             }17         }18         19         return res20     }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             continue31         }32         return res33     }34     35     func maxnums(_ num1 : [Int],_ num2 : [Int],_ k : Int) -> [Int] {36         var res = [Int]()37         var i = 0,j = 038         for _ in 0..<k {39             if isGreater(num1,num2,i,j) {40                 res.append(num1[i])41                 i+=142             }else {43                 res.append(num2[j])44                 j+=145             }46         }47         48         return res49     }50     51     func isGreater(_ nums1: [Int],_ nums2 : [Int],_ i : Int,_ j : Int) -> Bool {52         var i = i,j = j53         while i < nums1.count,j < nums2.count && nums1[i] == nums2[j] {54             i+=155             j+=156         }57         58         return j == nums2.count || (i < nums1.count && nums1[i] > nums2[j])59     }60 }