2023-12-09：用 go 语言，给你两个整数数组 arr1 和 arr2，返回使 arr1 严格递增所需要的最小「操作」数（可能为 0）。每一步「操作」中，你可以分别从 arr1 和 arr2

作者：福大大架构师每日一题

2023-12-09
北京
本文字数：3209 字
阅读完需：约 11 分钟

2023-12-09：用 go 语言，给你两个整数数组 arr1 和 arr2，

返回使 arr1 严格递增所需要的最小「操作」数（可能为 0）。

每一步「操作」中，你可以分别从 arr1 和 arr2 中各选出一个索引，

分别为 i 和 j，0 <= i < arr1.length 和 0 <= j < arr2.length，

然后进行赋值运算 arr1[i] = arr2[j]。如果无法让 arr1 严格递增，请返回 -1。

输入：arr1 = [1,5,3,6,7], arr2 = [4,3,1]。

输出：2。

答案 2023-12-09：

灵捷3.5

大体过程如下：

算法 1（makeArrayIncreasing1）：

1.对 arr2 进行排序并去除重复元素，生成新的数组 help，并统计 cnt 为 help 的长度。

2.通过递归函数 process1 来计算从 arr1 的索引 i 开始到结尾的最小操作数。初始时，i 为-1。

3.在 process1 中，通过二分查找函数 find，在 arr2 中找到第一个大于 cur 的元素的索引 f。

4.使用循环遍历 arr1 中从 i+1 到末尾的元素。

若当前元素大于 cur，则说明可以选择该元素，继续递归调用 process1，并将操作数 times 加 1。
若 f 不等于-1 且小于 arr2 的长度，更新 cur 为 arr2[f]，同时 f 加 1，times 加 1。
若 f 等于-1 或大于等于 arr2 的长度，跳出循环。

5.返回递归调用的结果 ans，即最小操作数。

算法 2（makeArrayIncreasing2）：

1.对 arr2 进行排序并去除重复元素，生成新的数组 help，并统计 cnt 为 help 的长度。

2.创建 dp 数组，初始值为-1。

3.通过递归函数 process2 来计算从 arr1 的索引 i 开始到结尾的最小操作数。同时，使用 dp 数组记录已计算过的结果，以便后续查询。

4.在 process2 中，若 dp[i+1]不等于-1，直接返回 dp[i+1]。

5.剩下的过程与 makeArrayIncreasing1 基本相同，只是将递归调用替换为对 dp 数组的查询和更新。

6.返回递归调用的结果 ans，同时将其保存到 dp[i+1]中。

算法 3（makeArrayIncreasing3）：

1.对 arr2 进行排序并去除重复元素，生成新的数组 arr2，并统计 m 为 arr2 的长度。

2.创建 dp 数组，长度为 n+2，并初始化为最大整数。

3.从 arr1 末尾向前遍历，使用循环计算从索引 i 开始到结尾的最小操作数。

初始化 cur 为 arr1[i]，f 为在 arr2 中找到第一个大于 cur 的元素的索引。
初始化 dp[i+1]为最大整数，times 为 0。
使用循环遍历 arr1 中从 i+1 到末尾的元素，操作步骤与 makeArrayIncreasing1 和 makeArrayIncreasing2 相似。
若 dp[j+1]不等于最大整数，更新 dp[i+1]为 times+dp[j+1]与 dp[i+1]中的较小值。
若 f 不等于-1 且小于 m，更新 cur 为 arr2[f]，同时 f 加 1，times 加 1。
若 f 等于-1 或大于等于 m，跳出循环。

4.若 dp[0]等于最大整数，返回-1；否则返回 dp[0]作为最小操作数。

时间复杂度分析：

算法 1 和算法 2 的时间复杂度为 O(n * m)，其中 n 和 m 分别为 arr1 和 arr2 的长度，因为每个元素都需要遍历一次。
算法 3 的时间复杂度为 O(n * m + m * log(m))，其中 m 为 arr2 的长度，因为要对 arr2 进行排序并进行二分查找。

额外空间复杂度分析：

算法 1 和算法 2 的额外空间复杂度为 O(m)，用于存储去重后的 arr2。
算法 3 的额外空间复杂度为 O(m)，用于存储去重后的 arr2，并且使用了一个大小为 n+2 的 dp 数组来记录中间结果。

go 完整代码如下：

package main
import (  "fmt"  "math"  "sort")
func makeArrayIncreasing1(arr1 []int, arr2 []int) int {  sort.Ints(arr2)  cnt := 1  for i := 1; i < len(arr2); i++ {    if arr2[i] != arr2[i-1] {      cnt++    }  }  help := make([]int, cnt)  help[0] = arr2[0]  for i, j := 1, 1; i < len(arr2); i++ {    if arr2[i] != arr2[i-1] {      help[j] = arr2[i]      j++    }  }  ans := process1(arr1, help, -1)  if ans == math.MaxInt64 {    return -1  }  return ans}
func process1(arr1 []int, arr2 []int, i int) int {  if i == len(arr1) {    return 0  } else {    cur := 0    if i == -1 {      cur = math.MinInt64    } else {      cur = arr1[i]    }    f := find(arr2, cur)    ans := math.MaxInt64    times := 0    for j := i + 1; j <= len(arr1); j++ {      if j == len(arr1) || cur < arr1[j] {        next := process1(arr1, arr2, j)        if next != math.MaxInt64 {          ans = min(ans, times+next)        }      }      if f != -1 && f < len(arr2) {        cur = arr2[f]        f++        times++      } else {        break      }    }    return ans  }}
func find(arr2 []int, num int) int {  l := 0  r := len(arr2) - 1  ans := -1  for l <= r {    m := (l + r) / 2    if arr2[m] > num {      ans = m      r = m - 1    } else {      l = m + 1    }  }  return ans}
func min(a, b int) int {  if a < b {    return a  }  return b}
func makeArrayIncreasing2(arr1 []int, arr2 []int) int {  sort.Ints(arr2)  cnt := 1  for i := 1; i < len(arr2); i++ {    if arr2[i] != arr2[i-1] {      cnt++    }  }  help := make([]int, cnt)  help[0] = arr2[0]  for i, j := 1, 1; i < len(arr2); i++ {    if arr2[i] != arr2[i-1] {      help[j] = arr2[i]      j++    }  }  dp := make([]int, len(arr1)+1)  for i := range dp {    dp[i] = -1  }  ans := process2(arr1, help, -1, dp)  if ans == math.MaxInt64 {    return -1  }  return ans}
func process2(arr1 []int, arr2 []int, i int, dp []int) int {  if i == len(arr1) {    return 0  } else {    if dp[i+1] != -1 {      return dp[i+1]    }    cur := 0    if i == -1 {      cur = math.MinInt64    } else {      cur = arr1[i]    }    f := find(arr2, cur)    ans := math.MaxInt64    times := 0    for j := i + 1; j <= len(arr1); j++ {      if j == len(arr1) || cur < arr1[j] {        next := process2(arr1, arr2, j, dp)        if next != math.MaxInt64 {          ans = min(ans, times+next)        }      }      if f != -1 && f < len(arr2) {        cur = arr2[f]        f++        times++      } else {        break      }    }    dp[i+1] = ans    return ans  }}
func makeArrayIncreasing3(arr1 []int, arr2 []int) int {  sort.Ints(arr2)  m := 1  for i := 1; i < len(arr2); i++ {    if arr2[i] != arr2[m-1] {      arr2[m] = arr2[i]      m++    }  }  n := len(arr1)  dp := make([]int, n+2)  for i := n - 1; i >= -1; i-- {    cur := 0    if i == -1 {      cur = math.MinInt64    } else {      cur = arr1[i]    }    f := find3(arr2, m, cur)    dp[i+1] = math.MaxInt64    times := 0    for j := i + 1; j <= n; j++ {      if j == n || cur < arr1[j] {        if dp[j+1] != math.MaxInt64 {          dp[i+1] = min(dp[i+1], times+dp[j+1])        }      }      if f != -1 && f < m {        cur = arr2[f]        f++        times++      } else {        break      }    }  }  if dp[0] == int(^uint(0)>>1) {    return -1  }  return dp[0]}
func find3(arr2 []int, size int, num int) int {  l := 0  r := size - 1  ans := -1  for l <= r {    m := (l + r) / 2    if arr2[m] > num {      ans = m      r = m - 1    } else {      l = m + 1    }  }  return ans}
func main() {  if true {    arr1 := []int{1, 5, 3, 6, 7}    arr2 := []int{4, 3, 1}    fmt.Println(makeArrayIncreasing1(arr1, arr2))  }  if true {    arr1 := []int{1, 5, 3, 6, 7}    arr2 := []int{4, 3, 1}    fmt.Println(makeArrayIncreasing2(arr1, arr2))  }  if true {    arr1 := []int{1, 5, 3, 6, 7}    arr2 := []int{4, 3, 1}    fmt.Println(makeArrayIncreasing3(arr1, arr2))  }}