題目
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]
有兩個整數(shù)數(shù)組 nums1 nums2 背率，元素值范圍是 0 ~ 9唇辨，給出 k <= nums1.count + nums2.count居灯。
創(chuàng)建一個長度為 k 的整數(shù)數(shù)組 res，使之符合以下條件：
- res 的元素取自 nums1 和 nums2
- res 的元素間相對位置與在 nums1 nums2 中的相對位置是保持不變的
- 多種組合中取值最大的 res
解題思路
基本思路是在 nums1 中取出 i 個值胎撇，在 nums2 中取出 k-i 個值，然后進(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 個值- 遍歷 nums跑杭，聲明臨時 res
- es 的尾元素與 nums 中的當(dāng)前元素 num 比較，若尾元素較小盗胀，則循環(huán)將 res 中小于 num 的尾元素艘蹋，直到尾元素不小于 num锄贼，或 res 與 nums 剩余元素個數(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] 時宅荤，i 和 j +1
-
循環(huán)結(jié)束后的情況：
- nums1 nums2 均沒有遍歷完屑迂，此時比較 nums1[i] > nums2[j]
- nums1 nums2 其中任意一個遍歷完，另一個沒有遍歷完冯键，沒有遍歷完的數(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])
詳情請看代碼注釋
代碼實現(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 需要取的最少個數(shù)，為了篩除負(fù)數(shù)句旱，與 0 取較大值
//nums1 取的最多個數(shù)即為 k 和 nums1.count 的較小值
for i in max(0, k-nums2.count) ... min(k, nums1.count) {
// 將 nums1 nums2 篩選 i k-i 個元素獲得新數(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ù)組 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 個元素腥泥，獲取最大數(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 的元素數(shù)量加上 nums 剩余的元素數(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
}
//將兩個數(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蛔外，移動序號 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] 時立宜，i j +1
while i < nums1.count && j < nums2.count && nums1[i] == nums2[j] {
i += 1
j += 1
}
//循環(huán)結(jié)束后的情況：
//1. nums1 nums2 均沒有遍歷完冒萄，此時比較 nums1[i] > nums2[j]
//2. nums1 nums2 其中任意一個遍歷完，另一個沒有遍歷完橙数，沒有遍歷完的數(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])
}
