leetcode刷题笔记321题 拼接最大数
地址：321. 拼接最大数
问题描述：
给定长度分别为 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]
object Solution {
def maxNumber(nums1: Array[Int], nums2: Array[Int], k: Int): Array[Int] = {
val n = nums1.length
val m = nums2.length
var res = Array.fill(k)(Int.MinValue)
//用于枚举nums中k个按照字典序的数组
def maxArray(nums: Array[Int], k: Int): Array[Int] = {
val res = Array.fill(k)(0)
//println(res.mkString)
val length = nums.length
var j = 0
for (i <- 0 to length-1) {
val x = nums(i)
while (j > 0 && res(j-1) < x && j + length - i > k) j -= 1
//这里注意检查合法性
if (j < k) {
res(j) = x
j += 1
}
}
return res
}
//用于对总数为k的a b两数组按照字典序进行合并
def merge(a: Array[Int], b: Array[Int]): Array[Int] = {
var i = 0
var j = 0
val res = Array.fill(k)(0)
while (i < a.length && j < b.length) {
if (a(i) > b(j)){
res(i+j) = a(i)
i += 1
} else if (a(i) < b(j)){
res (i+j) = b(j)
j += 1
} else {
//这里是对于 == 情况的处理
//使用k标记最多多少位相同
//同时判断是否有数组被访问完
var k = 0
while (i + k < a.length && j + k < b.length && a(i+k) == b(j+k)){
k += 1
}
if (i + k == a.length) {
res (i+j) = b(j)
j += 1
} else if (j + k == b.length) {
res(i+j) = a(i)
i += 1
} else if (a(i+k) < b(j+k)) {
res (i+j) = b(j)
j += 1
} else {
res(i+j) = a(i)
i += 1
}
}
}
//对未进行合并的结果进行合并
while (i < a.length) {
res(i+j) = a(i)
i += 1
}
while (j < b.length) {
res(i+j) = b(j)
j += 1
}
return res
}
def max(a: Array[Int], b: Array[Int]): Array[Int] = {
val length = a.length
for (i <- 0 to length-1) {
if (a(i) > b(i)) {
return a
} else if (a(i) < b(i)) {
return b
}
}
return a
}
for (i <- math.max(0, k-m) to math.min(k, n)) {
val a = maxArray(nums1, i)
val b = maxArray(nums2, k-i)
//println("-----------------")
//println("a: " + a.mkString(" "))
//println("b: " + b.mkString(" "))
val c = merge(a,b)
//println("c: " + c.mkString(" "))
res = max(res, c)
//println("res: " + res.mkString(" "))
}
return res
}
}
//import "fmt"
func maxNumber(nums1 []int, nums2 []int, k int) []int {
n := len(nums1)
m := len(nums2)
res := make([]int, k)
for i := max(0, k-m); i <= min(k, n); i++ {
a := maxArray(nums1, i)
b := maxArray(nums2, k-i)
c := merge(a, b)
if greater(res, c) == false {
res = c
}
}
return res
}
func maxArray(nums []int, k int) []int {
length := len(nums)
res := make([]int, k)
for i, j := 0, 0; i < length; i++ {
x := nums[i]
for (j > 0 && res[j-1] < x && j + length - i > k) {j -= 1}
if j < k {
res[j] = x
j += 1
}
}
return res
}
func merge(a, b []int) []int {
length := len(a) + len(b)
res := make([]int, length)
i, j := 0, 0
for k := range res {
if greater(a[i:], b[j:]){
res[k] = a[i]
i += 1
} else {
res[k] = b[j]
j += 1
}
}
return res
}
func greater(a, b []int) bool {
min_len := len(a)
if len(b) < min_len {
min_len = len(b)
}
for i := 0; i < min_len; i++ {
if a[i] > b[i] {
return true
}
if a[i] < b[i] {
return false
}
}
return min_len == len(b)
}
func max (a, b int) int {
if a > b {
return a
} else {
return b
}
}
func min (a, b int) int {
if a < b {
return a
} else {
return b
}
}