拼接最大数
给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。
求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。
示例 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]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/create-maximum-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。如题目所说，该问题需要从两个数组中一共取k个数，不修改取出数的相对位置前提下组成一个最大的数。该问题与前几天周赛中找出具有竞争力的子序列类似，不过该问题是上一问题的升级版，找出具有竞争力的子序列只需从一个数组中找到长度为k的最小的一个数，因此只要我们枚举出nums1，和nums2中所选序列的长度，然后依次从nums1，nums2中找到对应长度的子序列并将其合并，再选择出合并之后值最大的序列即可。
再回到前一个问题，如何找到nums中长度为k的序列？由于想让序列值最大，我们应该尽可能的让大的值位于前面，因此很容易想到使用单调栈这种数据结构求解非递增子序列，不过求解时需要注意的是要满足长度k。因此从栈顶弹出元素时需要判断当前栈中元素加之后可用元素的数目能否达到k，只有大于k时才能往出弹较小的栈顶元素。
之后如何进行合并呢，一个直观的思路是利用归并排序从大到小排即可，但是如此操作并不适合当前两节点相等的情况，例如：
seq1 = [1,2]
seq2 = [1]合并之后应为[1, 2, 1]而不是[1, 1, 2]。因此不能武断的使用归并排序的思路，应该判断从当前位置开始序列字典序的大小，应该选择字典序大序列的当前位置。
func maxNumber(nums1 []int, nums2 []int, k int) []int {
ans := make([]int, k)
for i := 0; i <= k; i++{
if i > len(nums1) || k - i > len(nums2){
continue
}
sequence1 := getMaxSequence(nums1, i)
sequence2 := getMaxSequence(nums2, k - i)
sequence := merge(sequence1, sequence2)
// fmt.Println(sequence1, sequence2, sequence, ans)
if less(ans, sequence, 0, 0){
ans = sequence
}
}
return ans
}
// 找到nums中长度为k的最大子序列
func getMaxSequence(nums []int, k int) []int{
stack := make([]int, 0, len(nums))
for idx, val := range nums{
// len(nums) - idx
for len(stack) > 0 && len(nums) - idx + len(stack) > k && stack[len(stack) - 1] < val{
stack = stack[0:len(stack) - 1]
}
stack = append(stack, val);
}
return stack[0:k]
}
// 合并两个非递减序列
func merge(nums1, nums2 []int) []int{
if len(nums1) == 0{
return nums2
}
if len(nums2) == 0{
return nums1
}
i, j := 0, 0
ans := make([]int, 0, len(nums1) + len(nums2))
for i < len(nums1) && j < len(nums2){
// 此处比较序列大小而不是比较单个字符的大小是为了处理两当前字母相同时的情况
// [1,2][1] 结果应该为[1,2,1] 而不是 [1,1,2]
if less(nums1, nums2, i, j){
ans = append(ans, nums2[j])
j++
}else{
ans = append(ans, nums1[i])
i++
}
}
for i < len(nums1){
ans = append(ans, nums1[i])
i++
}
for j < len(nums2){
ans = append(ans, nums2[j])
j++
}
return ans
}
// 比较nums1[i,:]是否小于nums2[j,:]
func less(nums1, nums2 []int, i, j int)bool{
for i < len(nums1) && j < len(nums2){
if nums1[i] < nums2[j]{
return true
}else if nums1[i] > nums2[j]{
return false
}
i++
j++
}
// nums1没了 nums2还有 nums2就更大一点
if j < len(nums2){
return true
}
return false
}时间复杂度O（k * （m + n + k ^2））
枚举长度为O（k），找到nums1，nums2中给定长度最大子序列的的时间复杂度依次为O（m），O（n）,合并过程中世间复杂度为O（k^2）
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-12-02，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读