2026-02-18：拆分合并数组。用go语言，给定两个长度均为 n 的整数数组 nums1 和 nums2。你可以对 nums1 进行若干次如下“剪切-粘贴”操作

福大大架构师每日一题

发布于 2026-03-04 18:39:16

200

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2026-02-18：拆分合并数组。用go语言，给定两个长度均为 n 的整数数组 nums1 和 nums2。你可以对 nums1 进行若干次如下“剪切-粘贴”操作：

• 选定一个连续区间 nums1[L..R]（含端点）。
• 将该区间从数组中摘出，数组剩下前半段 nums1[0..L-1]（若 L=0 则为空）和后半段 nums1[R+1..n-1]（若 R=n-1 则为空）。
• 把摘出的那段（保持原有顺序）插入到剩余数组的任意位置，可以放在任意两个元素之间，也可以放到开头或末尾。

问：要把 nums1 变为 nums2，至少需要进行多少次这样的剪切-粘贴操作？

2 <= n == nums1.length == nums2.length <= 6。

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

nums2 是 nums1 的一个排列。

输入: nums1 = [1,1,2,3,4,5], nums2 = [5,4,3,2,1,1]。

输出: 3。

解释:

移除下标 0 - 2 处的 [1,1,2]；剩余 [3,4,5]；将 [1,1,2] 插入到位置 2，得到 [3,4,1,1,2,5]。

移除下标 1 - 3 处的 [4,1,1]；剩余 [3,2,5]；将 [4,1,1] 插入到位置 3，得到 [3,2,5,4,1,1]。

移除下标 0 - 1 处的 [3,2]；剩余 [5,4,1,1]；将 [3,2] 插入到位置 2，得到 [5,4,3,2,1,1]。

题目来自力扣3690。

解题思路与步骤

1. 问题转化
- • 给定两个长度相同的数组 nums1 和 nums2，nums2 是 nums1 的一个排列。
- • 允许对 nums1 进行操作：选择一个连续区间，将其切出，然后插入到剩余数组的任意位置（包括开头、中间、末尾）。
- • 目标：用最少的操作次数将 nums1 变成 nums2。
2. 状态表示
- • 由于数组长度 n ≤ 6，最多有 6! 种排列，但因为有重复元素，实际状态数更少。
- • 为了在 BFS 中表示数组的状态，需要对数组进行离散化编码。
- • 先将 nums1 排序得到 sorted，然后用每个元素在 sorted 中的索引表示该元素。
- • 每个元素用 3 位二进制表示（因为 n ≤ 6，索引 0~5，3 位足够）。
- • 将整个数组编码成一个整数，例如 nums = [1,1,2,3,4,5]，sorted = [1,1,2,3,4,5]，编码后每个元素用它在 sorted 中的索引表示，然后拼接成一个整数。
3. BFS 搜索
- • 从初始状态 val1（nums1 的编码）开始，目标状态是 val2（nums2 的编码）。
- • 使用队列进行 BFS，每一层代表一次操作。
- • 对于当前状态 a，枚举所有可能的剪切区间 [l, r]（0 ≤ l ≤ r < n）：
  - • 从 a 中提取出区间 sub。
  - • 将 a 分成三部分：左边（l 之前）、区间、右边（r 之后）。
  - • 将区间 sub 插入到剩余数组（左边+右边）的任意位置（0 到 n - (r - l + 1) 个位置）。
  - • 生成新的状态 c。
- • 如果 c 等于 val2，则返回当前步数 ans。
- • 否则，如果 c 未被访问过，则加入队列，继续搜索。
4. 编码与解码
- • encode 函数：将数组 nums 中每个元素替换为它在 sorted 中的索引，然后按 3 位一组拼接成整数。
- • 在 BFS 中，通过位运算来提取区间和拼接新状态，避免手动构造数组，提高效率。
5. 搜索终止
- • BFS 第一次到达目标状态时，对应的步数就是最少操作次数。
- • 由于状态空间有限，BFS 一定能找到解。

时间复杂度分析

• 状态数：最多有 n! 种排列，n ≤ 6，所以状态数 ≤ 720。
• 对于每个状态，枚举所有可能的剪切区间：区间数量为 O(n²) = 36。
• 对于每个区间，枚举插入位置：最多 O(n) = 6。
• 所以每个状态扩展出的新状态数 ≤ 36 × 6 = 216。
• BFS 遍历所有状态，总操作次数 ≤ 720 × 216 ≈ 15 万次，实际更少。
• 每次操作都是位运算，常数很小。
• 总时间复杂度：O(n! × n³)，但实际运行很快，因为 n 很小。

额外空间复杂度分析

• 需要存储所有访问过的状态：最多 720 个状态，每个状态用一个整数表示，map 开销稍大，但仍是 O(状态数)。
• 队列中最多同时存储一层状态，最坏情况下可能存储所有状态，但也是 O(状态数)。
• 总额外空间复杂度：O(n!)，即 O(720) 级别，非常小。

总结

• 使用 BFS + 状态压缩（编码）求解最少剪切-粘贴次数。
• 时间复杂度：O(n! × n³)
• 空间复杂度：O(n!)

Go完整代码如下：

package main

import (
    "fmt"
    "slices"
    "sort"
)

func encode(nums, sorted []int) (res int) {
    for i, x := range nums {
        res |= sort.SearchInts(sorted, x) << (i * 3)
    }
    return
}

func minSplitMerge(nums1, nums2 []int)int {
    if slices.Equal(nums1, nums2) {
        return0
    }

    n := len(nums1)
    sorted := slices.Clone(nums1) // 用于离散化
    slices.Sort(sorted)

    val1 := encode(nums1, sorted)
    val2 := encode(nums2, sorted)

    vis := map[int]bool{val1: true}
    q := []int{val1}
    for ans := 1; ; ans++ {
        tmp := q
        q = nil
        for _, a := range tmp {
            for r := 1; r <= n; r++ { // 为方便实现，先枚举 r，再枚举 l
                t := a & (1<<(r*3) - 1)
                for l := range r {
                    sub := t >> (l * 3)
                    b := a&(1<<(l*3)-1) | a>>(r*3)<<(l*3) // 从 a 中移除 sub
                    for i := range n - r + l + 1 {
                        c := b&(1<<(i*3)-1) | sub<<(i*3) | b>>(i*3)<<((i+r-l)*3)
                        if c == val2 {
                            return ans
                        }
                        if !vis[c] {
                            vis[c] = true
                            q = append(q, c)
                        }
                    }
                }
            }
        }
    }
}

func main() {
    nums1 := []int{1, 1, 2, 3, 4, 5}
    nums2 := []int{5, 4, 3, 2, 1, 1}
    result := minSplitMerge(nums1, nums2)
    fmt.Println(result)
}

Python完整代码如下：

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

import sys
from typing import List
import bisect


def encode(nums: List[int], sorted_vals: List[int]) -> int:
    """将数组编码为整数，每3位存储一个元素的索引"""
    res = 0
    for i, x in enumerate(nums):
        # bisect_left 相当于 Go 的 sort.SearchInts
        idx = bisect.bisect_left(sorted_vals, x)
        res |= idx << (i * 3)
    return res


def min_split_merge(nums1: List[int], nums2: List[int]) -> int:
    """计算通过分割和合并操作将 nums1 转换为 nums2 的最小步数"""
    if nums1 == nums2:
        return0

    n = len(nums1)
    # 用于离散化
    sorted_vals = nums1.copy()
    sorted_vals.sort()

    val1 = encode(nums1, sorted_vals)
    val2 = encode(nums2, sorted_vals)

    visited = {val1: True}
    queue = [val1]
    ans = 1

    while queue:
        tmp = queue
        queue = []
        for a in tmp:
            # 枚举 r (子数组右边界，1-based)
            for r in range(1, n + 1):
                # 提取低 r*3 位作为 t
                t = a & ((1 << (r * 3)) - 1)
                # 枚举 l (子数组左边界，0-based)
                for l in range(r):
                    sub = (t >> (l * 3)) & ((1 << ((r - l) * 3)) - 1)

                    # 从 a 中移除子数组 [l, r)
                    # 低 l*3 位保持不变
                    low_mask = (1 << (l * 3)) - 1
                    low_part = a & low_mask
                    # 高位部分右移
                    high_part = a >> (r * 3)
                    b = low_part | (high_part << (l * 3))

                    # 将子数组插入到各个可能的位置
                    for i in range(n - r + l + 1):
                        # 构建新数组 c
                        # 低 i*3 位来自 b 的低位
                        c_low = b & ((1 << (i * 3)) - 1)
                        # 中间插入子数组
                        c_mid = sub << (i * 3)
                        # 高位来自 b 的剩余部分
                        c_high = (b >> (i * 3)) << ((i + r - l) * 3)
                        c = c_low | c_mid | c_high

                        if c == val2:
                            return ans
                        if c not in visited:
                            visited[c] = True
                            queue.append(c)
        ans += 1

    return-1  # 理论上不会执行到这里


def main():
    nums1 = [1, 1, 2, 3, 4, 5]
    nums2 = [5, 4, 3, 2, 1, 1]
    result = min_split_merge(nums1, nums2)
    print(result)


if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map>

using namespace std;

int encode(const vector<int>& nums, const vector<int>& sorted) {
    int res = 0;
    for (int i = 0; i < nums.size(); i++) {
        // lower_bound 相当于 Go 的 sort.SearchInts
        int idx = lower_bound(sorted.begin(), sorted.end(), nums[i]) - sorted.begin();
        res |= idx << (i * 3);
    }
    return res;
}

int minSplitMerge(vector<int>& nums1, vector<int>& nums2) {
    if (nums1 == nums2) {
        return0;
    }

    int n = nums1.size();
    vector<int> sorted = nums1; // 用于离散化
    sort(sorted.begin(), sorted.end());

    int val1 = encode(nums1, sorted);
    int val2 = encode(nums2, sorted);

    unordered_map<int, bool> vis;
    vis[val1] = true;
    vector<int> q;
    q.push_back(val1);

    for (int ans = 1; ; ans++) {
        vector<int> tmp = q;
        q.clear();

        for (int a : tmp) {
            for (int r = 1; r <= n; r++) { // 为方便实现，先枚举 r，再枚举 l
                int t = a & ((1 << (r * 3)) - 1);
                for (int l = 0; l < r; l++) {
                    int sub = (t >> (l * 3)) & ((1 << ((r - l) * 3)) - 1);

                    // 从 a 中移除 sub
                    int low_mask = (1 << (l * 3)) - 1;
                    int low_part = a & low_mask;
                    int high_part = a >> (r * 3);
                    int b = low_part | (high_part << (l * 3));

                    // 将子数组插入到各个可能的位置
                    for (int i = 0; i < n - r + l + 1; i++) {
                        int c_low = b & ((1 << (i * 3)) - 1);
                        int c_mid = sub << (i * 3);
                        int c_high = (b >> (i * 3)) << ((i + r - l) * 3);
                        int c = c_low | c_mid | c_high;

                        if (c == val2) {
                            return ans;
                        }

                        if (vis.find(c) == vis.end()) {
                            vis[c] = true;
                            q.push_back(c);
                        }
                    }
                }
            }
        }
    }
}

int main() {
    vector<int> nums1 = {1, 1, 2, 3, 4, 5};
    vector<int> nums2 = {5, 4, 3, 2, 1, 1};
    int result = minSplitMerge(nums1, nums2);
    cout << result << endl;
    return0;
}