2026-03-16：转换数组的最少操作次数。用go语言，给定两个整数数组：第一个长度为 n，第二个长度为 n+1。你可以对第一个数组反复施行三类

福大大架构师每日一题

发布于 2026-03-31 21:08:36

740

2026-03-16：转换数组的最少操作次数。用go语言，给定两个整数数组：第一个长度为 n，第二个长度为 n+1。你可以对第一个数组反复施行三类操作中的任意一种——选择一个下标 i，使该位置的元素加 1、或减 1、或将该位置当前的值复制并追加到数组末尾。问：要把第一个数组变为第二个数组，至少需要多少次这样的操作？请返回最小操作次数。

1 <= n == nums1.length <= 100000。

nums2.length == n + 1。

1 <= nums1[i], nums2[i] <= 100000。

输入: nums1 = [2,8], nums2 = [1,7,3]。

输出: 4。

解释:

步骤	i	操作	nums1[i]	更新后的 nums1
1	0	追加	-	[2, 8, 2]
2	0	减少	减少到 1	[1, 8, 2]
3	1	减少	减少到 7	[1, 7, 2]
4	2	增加	增加到 3	[1, 7, 3]

因此，经过 4 次操作后，nums1 转换为 nums2。

题目来自力扣3724。

核心解题思路（分两大块）

我们要把 nums1 从长度 n 变成 n+1，所以必须且只需要执行 1 次「追加操作」。整个问题拆成 2 部分计算：

1. 基础操作数：把 nums1 前 n 个元素，改成 nums2 前 n 个元素需要的加减次数。
2. 最优追加节省：选择哪一个位置进行追加，能让总操作数最少（追加后新元素变成 nums2 最后一个元素的成本最低）。

以示例输入分步讲解

输入： nums1 = [2, 8] （n=2） nums2 = [1, 7, 3] （长度 3 = n+1） nums2 最后一个元素是 3（我们叫它 target）。

第一步：计算「基础加减操作数」

把 nums1 前 2 个元素，改成 nums2 前 2 个元素：

• nums1[0] = 2 → nums2[0] = 1：减 1 → 1 次操作
• nums1[1] = 8 → nums2[1] = 7：减 1 → 1 次操作 ✅ 基础总操作数 = 1 + 1 = 2

第二步：必须执行 1 次「追加操作」

因为要把长度从 2 变 3，必须追加 1 次，这一步固定消耗： ✅ 追加操作数 = 1

目前累计：2 + 1 = 3 次。

第三步：处理追加后的新元素（最关键）

追加的新元素，最终要变成 nums2 最后一个数：3。我们可以选择从 nums1 任意一个位置复制值进行追加，不同选择成本不同：

我们遍历每一个位置，计算**「从该位置复制追加 → 改成 target=3」的最小成本**：

位置 0 分析：

原 nums1[0] 最终会改成 1

• 复制追加的值 = 1
• 要变成 3：需要加 2 → 成本 2

位置 1 分析：

原 nums1[1] 最终会改成 7

• 复制追加的值 = 7
• 要变成 3：需要减 4 → 成本 4

✅ 所有位置里，最小的修改成本是 2（选位置0追加）

第四步：总最少操作数

基础加减(2) + 追加(1) + 最小修改成本(2) = 4 和题目输出完全一致！

通用完整解题步骤（所有输入都适用）

1. 确定目标值 取出 nums2 最后一个元素，记为 target（这是 nums1 追加后新元素必须变成的值）。
2. 计算基础修改成本 遍历 nums1 和 nums2 的前 n 个元素，每个位置计算： 当前元素 → 目标元素 需要加减多少次，全部累加。这是把前 n 位对齐的固定成本。
3. 固定追加成本 因为长度要从 n → n+1，必须追加 1 次，成本 +1。
4. 计算最优追加位置的最小成本 遍历每一个下标 i：
- • 该位置最终会被修改为 nums2[i]
- • 复制这个值追加到末尾
- • 计算：这个复制值 → target 需要的加减次数记录所有位置里最小的那个成本。
5. 总和就是答案 总操作数 = 基础修改成本 + 追加成本 + 最优追加修改成本

时间复杂度 & 空间复杂度

1. 时间复杂度

• 我们只对数组做了一次从头到尾的遍历
• 数组长度最大是 10⁵
• 遍历中所有操作都是 O(1) 的简单计算

✅ 时间复杂度：O(n) （n 是 nums1 的长度）

2. 额外空间复杂度

• 只使用了几个变量存储：基础成本、最小成本、目标值
• 没有开辟任何与数组长度相关的额外空间

✅ 额外空间复杂度：O(1) （常数级空间，不随输入规模变大）

总结

1. 解题核心：必须追加1次，拆分「基础修改」+「追加」+「新元素修改」三部分；
2. 最优解关键：选复制后改成 target 成本最小的位置追加；
3. 效率：O(n) 时间 + O(1) 额外空间，完全适配题目 10万数据规模。

Go完整代码如下：

package main

import (
    "fmt"
    "math"
)

func minOperations(nums1, nums2 []int)int64 {
    target := nums2[len(nums2)-1]
    ans := 1// 把元素追加到 nums1 的末尾需要一次操作
    mn := math.MaxInt
    for i, x := range nums1 {
        y := nums2[i]
        if x > y {
            x, y = y, x // 保证 x <= y，简化后续逻辑
        }
        ans += y - x
        // 如果 target 在 [x,y] 中，那么在从 x 变成 y 的过程中，可以顺带把 target 追加到 nums1 的末尾，代价为 0
        // 如果 target < x，代价为 x-target
        // 如果 target > y，代价为 target-y
        mn = min(mn, max(x-target, target-y))
    }
    returnint64(ans + max(mn, 0)) // 如果 target 在 [x,y] 中，上面可能会算出负数
}

func main() {
    nums1 := []int{2, 8}
    nums2 := []int{1, 7, 3}
    result := minOperations(nums1, nums2)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

import math

defminOperations(nums1, nums2):
    target = nums2[len(nums2)-1]
    ans = 1# 把元素追加到 nums1 的末尾需要一次操作
    mn = math.inf
    for i, x inenumerate(nums1):
        y = nums2[i]
        if x > y:
            x, y = y, x  # 保证 x <= y，简化后续逻辑
        ans += y - x
        # 如果 target 在 [x,y] 中，那么在从 x 变成 y 的过程中，可以顺带把 target 追加到 nums1 的末尾，代价为 0
        # 如果 target < x，代价为 x-target
        # 如果 target > y，代价为 target-y
        mn = min(mn, max(x - target, target - y))
    
    return ans + max(mn, 0)  # 如果 target 在 [x,y] 中，上面可能会算出负数

# 测试
nums1 = [2, 8]
nums2 = [1, 7, 3]
result = minOperations(nums1, nums2)
print(result)

C++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

usingnamespace std;

long long minOperations(vector<int>& nums1, vector<int>& nums2) {
    int target = nums2[nums2.size() - 1];
    longlong ans = 1;  // 把元素追加到 nums1 的末尾需要一次操作
    int mn = INT_MAX;

    for (int i = 0; i < nums1.size(); i++) {
        int x = nums1[i];
        int y = nums2[i];
        if (x > y) {
            swap(x, y);  // 保证 x <= y，简化后续逻辑
        }
        ans += y - x;
        // 如果 target 在 [x,y] 中，那么在从 x 变成 y 的过程中，可以顺带把 target 追加到 nums1 的末尾，代价为 0
        // 如果 target < x，代价为 x-target
        // 如果 target > y，代价为 target-y
        mn = min(mn, max(x - target, target - y));
    }

    return ans + max(mn, 0);  // 如果 target 在 [x,y] 中，上面可能会算出负数
}

int main() {
    vector<int> nums1 = {2, 8};
    vector<int> nums2 = {1, 7, 3};
    longlong result = minOperations(nums1, nums2);
    cout << result << endl;
    return0;
}