Medium
题目描述
给定两个长度为 n 的整数数组 nums1 和 nums2。你可以对 nums1 执行任意次数的分割合并操作：
- 选择一个子数组
nums1[L..R] - 移除该子数组，留下前缀
nums1[0..L-1]（如果 L = 0 则为空）和后缀nums1[R+1..n-1]（如果 R = n - 1 则为空） - 将移除的子数组（保持原始顺序）重新插入到剩余数组的任意位置（即任意两个元素之间、开头或末尾）
返回将 nums1 转换为 nums2 所需的最少分割合并操作次数。
示例 1：
输入：nums1 = [3,1,2], nums2 = [1,2,3]
输出：1
解释：
- 分割出子数组 [3]（L = 0, R = 0）；剩余数组为 [1,2]
- 将 [3] 插入末尾；数组变为 [1,2,3]
示例 2：
输入：nums1 = [1,1,2,3,4,5], nums2 = [5,4,3,2,1,1]
输出：3
解释：
- 移除索引 0-2 的 [1,1,2]；剩余 [3,4,5]；在位置 2 插入 [1,1,2]，得到 [3,4,1,1,2,5]
- 移除索引 1-3 的 [4,1,1]；剩余 [3,2,5]；在位置 3 插入 [4,1,1]，得到 [3,2,5,4,1,1]
- 移除索引 0-1 的 [3,2]；剩余 [5,4,1,1]；在位置 2 插入 [3,2]，得到 [5,4,3,2,1,1]
约束条件：
2 <= n == nums1.length == nums2.length <= 6-10^5 <= nums1[i], nums2[i] <= 10^5nums2是nums1的一个排列
解题思路
这是一个典型的状态空间搜索问题。由于数组长度最大为6，状态空间相对较小，我们可以使用BFS找到最短路径。
核心思路：
- 状态表示：将每个数组状态作为搜索节点
- BFS搜索：从初始状态
nums1开始，目标状态为nums2 - 状态转移：对于当前状态，枚举所有可能的子数组
[L, R]，移除后在所有位置重新插入 - 去重优化：使用哈希表记录已访问状态，避免重复搜索
详细步骤：
- 初始化队列，放入起始状态和操作次数0
- 使用集合记录已访问的状态（将数组转为元组作为键）
- 对每个出队状态，生成所有可能的下一状态：
- 枚举所有子数组
[L, R] - 移除该子数组，得到剩余部分
- 在剩余部分的每个位置插入被移除的子数组
- 枚举所有子数组
- 当找到目标状态时返回操作次数
由于约束条件保证了较小的搜索空间，BFS能够高效找到最优解。
代码实现
class Solution {
public:
int minSplitMerge(vector<int>& nums1, vector<int>& nums2) {
queue<pair<vector<int>, int>> q;
set<vector<int>> visited;
q.push({nums1, 0});
visited.insert(nums1);
while (!q.empty()) {
auto [curr, ops] = q.front();
q.pop();
if (curr == nums2) {
return ops;
}
int n = curr.size();
// 枚举所有可能的子数组 [L, R]
for (int L = 0; L < n; L++) {
for (int R = L; R < n; R++) {
// 提取子数组
vector<int> subarray(curr.begin() + L, curr.begin() + R + 1);
// 构建剩余数组
vector<int> remaining;
for (int i = 0; i < L; i++) {
remaining.push_back(curr[i]);
}
for (int i = R + 1; i < n; i++) {
remaining.push_back(curr[i]);
}
// 在所有可能位置插入子数组
for (int pos = 0; pos <= remaining.size(); pos++) {
vector<int> next = remaining;
next.insert(next.begin() + pos, subarray.begin(), subarray.end());
if (visited.find(next) == visited.end()) {
visited.insert(next);
q.push({next, ops + 1});
}
}
}
}
}
return -1;
}
};
class Solution:
def minSplitMerge(self, nums1: List[int], nums2: List[int]) -> int:
from collections import deque
q = deque([(tuple(nums1), 0)])
visited = {tuple(nums1)}
while q:
curr_tuple, ops = q.popleft()
curr = list(curr_tuple)
if curr == nums2:
return ops
n = len(curr)
# 枚举所有可能的子数组 [L, R]
for L in range(n):
for R in range(L, n):
# 提取子数组
subarray = curr[L:R+1]
# 构建剩余数组
remaining = curr[:L] + curr[R+1:]
# 在所有可能位置插入子数组
for pos in range(len(remaining) + 1):
next_arr = remaining[:pos] + subarray + remaining[pos:]
next_tuple = tuple(next_arr)
if next_tuple not in visited:
visited.add(next_tuple)
q.append((next_tuple, ops + 1))
return -1
public class Solution {
public int MinSplitMerge(int[] nums1, int[] nums2) {
var q = new Queue<(int[], int)>();
var visited = new HashSet<string>();
q.Enqueue((nums1, 0));
visited.Add(string.Join(",", nums1));
while (q.Count > 0) {
var (curr, ops) = q.Dequeue();
if (curr.SequenceEqual(nums2)) {
return ops;
}
int n = curr.Length;
// 枚举所有可能的子数组 [L, R]
for (int L = 0; L < n; L++) {
for (int R = L; R < n; R++) {
// 提取子数组
var subarray = curr.Skip(L).Take(R - L + 1).ToArray();
// 构建剩余数组
var remaining = curr.Take(L).Concat(curr.Skip(R + 1)).ToArray();
// 在所有可能位置插入子数组
for (int pos = 0; pos <= remaining.Length; pos++) {
var next = remaining.Take(pos)
.Concat(subarray)
.Concat(remaining.Skip(pos))
.ToArray();
string nextKey = string.Join(",", next);
if (!visited.Contains(nextKey)) {
visited.Add(nextKey);
q.Enqueue((next, ops + 1));
}
}
}
}
}
return -1;
}
}
var minSplitMerge = function(nums1, nums2) {
const n = nums1.length;
const target = nums2.join(',');
if (nums1.join(',') === target) return 0;
const queue = [nums1.slice()];
const visited = new Set([nums1.join(',')]);
let operations = 0;
while (queue.length > 0) {
const size = queue.length;
operations++;
for (let i = 0; i < size; i++) {
const current = queue.shift();
// Try all possible subarrays [L, R]
for (let L = 0; L < n; L++) {
for (let R = L; R < n; R++) {
const subarray = current.slice(L, R + 1);
const remaining = [...current.slice(0, L), ...current.slice(R + 1)];
// Try inserting subarray at all possible positions
for (let pos = 0; pos <= remaining.length; pos++) {
const newArray = [...remaining.slice(0, pos), ...subarray, ...remaining.slice(pos)];
const newState = newArray.join(',');
if (newState === target) return operations;
if (!visited.has(newState)) {
visited.add(newState);
queue.push(newArray);
}
}
}
}
}
}
return -1;
};
复杂度分析
| 复杂度 | 分析 |
|---|---|
| 时间复杂度 | O(n! × n³) |
| 空间复杂度 | O(n! × n) |
说明：
- 时间复杂度：最多有 n! 种不同的数组排列状态，对每个状态需要枚举 O(n²) 个子数组，每个子数组有 O(n) 个插入位置
- 空间复杂度：队列和哈希表最多存储 O(n!) 个状态，每个状态占用 O(n) 空间