2023-12-09：用go语言，给你两个整数数组 arr1 和 arr2，返回使 arr1 严格递增所需要的

moonfdd 的个人博客 / 0 / 0 / 创建于 1年前

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))
    }
}