題目
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]
有兩個(gè)整數(shù)數(shù)組 nums1 nums2 ，元素值范圍是 0 ~ 9，給出 k <= nums1.count + nums2.count。
創(chuàng)建一個(gè)長度為 k 的整數(shù)數(shù)組 res，使之符合以下條件：
- res 的元素取自 nums1 和 nums2
- res 的元素間相對位置與在 nums1 nums2 中的相對位置是保持不變的
- 多種組合中取值最大的 res
解題思路
基本思路是在 nums1 中取出 i 個(gè)值，在 nums2 中取出 k-i 個(gè)值，然后進(jìn)行合并。
- i 的范圍為
max(0, k-nums2.count) ... min(k, nums1.count)，循環(huán)遍歷比較得最大的結(jié)果返回 - 循環(huán)中：
-
filterNums將 nums1 和 nums2 進(jìn)行篩選，分別得出 i 和 k-i 個(gè)值- 遍歷 nums，聲明臨時(shí) res
- es 的尾元素與 nums 中的當(dāng)前元素 num 比較，若尾元素較小，則循環(huán)將 res 中小于 num 的尾元素，直到尾元素不小于 num，或 res 與 nums 剩余元素個(gè)數(shù)等于 k
-
mergeArray將篩選出來的值進(jìn)行合并- nums1 nums2 篩選出來的整數(shù)數(shù)組為 newNums1 newNums2
- 用
isLarger比較 newNums1[i,newNums1.count] 和 newNums2[j,newNums2.count]，將較大者的當(dāng)前值加入到結(jié)果中
-
-
isLarger判斷 nums1[i,nums1.count] 是否大于 nums2[i,nums2.count]循環(huán)有效的 i j ，且 nums1[i] == nums2[j] 時(shí)，i 和 j +1
-
循環(huán)結(jié)束后的情況：
- nums1 nums2 均沒有遍歷完，此時(shí)比較 nums1[i] > nums2[j]
- nums1 nums2 其中任意一個(gè)遍歷完，另一個(gè)沒有遍歷完，沒有遍歷完的數(shù)組較大
- nums1 nums2 均遍歷完，結(jié)果相等
-
j == nums2.count 判斷 nums2 是否遍歷完，
- 若 nums2 遍歷完，nums1 也遍歷完，則相等返回 true ，覆蓋了情況 3
- 若 nums2 遍歷完，nums1 沒有遍歷完，則 nums1 大返回 true，覆蓋了情況 2
i < nums1.count && nums1[i] > nums2[j] 則覆蓋了情況 1
所以 return j == nums2.count || (i < nums1.count && nums1[i] > nums2[j])
詳情請看代碼注釋
代碼實(shí)現(xiàn)
Runtime: 340 ms
Memory: 21.1 MB
func maxNumber(_ nums1: [Int], _ nums2: [Int], _ k: Int) -> [Int] {
//初始化結(jié)果的容器 res
var res = [Int]()
//確定循環(huán)范圍，以 nums1 為基準(zhǔn)，k-nums2.count 為 nums1 需要取的最少個(gè)數(shù)，為了篩除負(fù)數(shù)，與 0 取較大值
//nums1 取的最多個(gè)數(shù)即為 k 和 nums1.count 的較小值
for i in max(0, k-nums2.count) ... min(k, nums1.count) {
// 將 nums1 nums2 篩選 i k-i 個(gè)元素獲得新數(shù)組 newNums1 newNums2
let newNums1 = self.filterNums(nums: nums1, k: i)
let newNums2 = self.filterNums(nums: nums2, k: k-i)
// 將 newNums1 newNums2 進(jìn)行合并，獲取臨時(shí)最大數(shù)組 tmp
let tmp = self.mergeArray(nums1: newNums1, nums2: newNums2)
print(newNums1,newNums2,i,k)
// 將 tmp 與 res 進(jìn)行比較，若 tmp 較大，則替換掉 res
if self.isLarger(nums1: tmp, nums2: res, i: 0, j: 0){
res = tmp
}
}
return res
}
//將 nums 篩選 k 個(gè)元素，獲取最大數(shù)組
func filterNums( nums: [Int], k: Int) -> [Int]{
// k 的邊界值處理
if k<=0 {
return []
}else if k >= nums.count{
return nums
}
//初始化結(jié)果的容器 res
var res = [Int]()
//遍歷 nums
for i in 0 ..< nums.count{
//獲取當(dāng)前數(shù)值 num
let num = nums[i]
//若 res 里的尾元素小于 num，并且 res.count + nums.count - i > k
// res.count + nums.count - i > k 表示 res 的元素?cái)?shù)量加上 nums 剩余的元素?cái)?shù)量大于 k ，這樣才可以繼續(xù)刪除尾元素
while !res.isEmpty && num > res.last! && res.count + nums.count - i > k {
res.removeLast()
}
//將 num 加入到 res
res.append(num)
}
//移除多余的元素
res.removeLast(res.count-k)
// 返回結(jié)果
return res
}
//將兩個(gè)數(shù)組合并成最大數(shù)組
func mergeArray(nums1: [Int], nums2: [Int]) -> [Int] {
//初始化結(jié)果的容器 res
var res = [Int]()
//初始化 nums1 nums2 的序號 i j 為 0
var i = 0 , j = 0
//共遍歷 nums1.count + nums2.count 次
for _ in 0 ..< nums1.count + nums2.count {
//比較 nums1[i,nums1.count] 和 nums2[j,nums2.count]
//將較大數(shù)組的當(dāng)前元素添加到 res，移動(dòng)序號 i 或者 j
if self.isLarger(nums1: nums1, nums2: nums2, i: i, j: j) {
res.append(nums1[i])
i += 1
}else{
res.append(nums2[j])
j += 1
}
}
//返回結(jié)果
return res
}
//判斷 nums1 是否大于 nums2
func isLarger(nums1: [Int], nums2: [Int], i : Int, j : Int) -> Bool {
var i = i , j = j
//循環(huán)有效的 i j ，且 nums1[i] == nums2[j] 時(shí)，i j +1
while i < nums1.count && j < nums2.count && nums1[i] == nums2[j] {
i += 1
j += 1
}
//循環(huán)結(jié)束后的情況：
//1. nums1 nums2 均沒有遍歷完，此時(shí)比較 nums1[i] > nums2[j]
//2. nums1 nums2 其中任意一個(gè)遍歷完，另一個(gè)沒有遍歷完，沒有遍歷完的數(shù)組較大
//3. nums1 nums2 均遍歷完，結(jié)果相等
// j == nums2.count 判斷 nums2 是否遍歷完，
//若 nums2 遍歷完，nums1 也遍歷完，則相等返回 true ，覆蓋了情況 3
//若 nums2 遍歷完，nums1 沒有遍歷完，則 nums1 大返回 true，覆蓋了情況 2
//i < nums1.count && nums1[i] > nums2[j] 則覆蓋了情況 1
return j == nums2.count || (i < nums1.count && nums1[i] > nums2[j])
}
