Hard
题目描述
给你一个二维整数数组 lists，其中每个 lists[i] 是一个非空的整数数组，按非递减顺序排序。
你可以重复选择两个列表 a = lists[i] 和 b = lists[j]，其中 i != j，并合并它们。合并 a 和 b 的成本为：
len(a) + len(b) + abs(median(a) - median(b))，其中 len 和 median 分别表示列表长度和中位数。
合并 a 和 b 后，从 lists 中移除 a 和 b，并将新的合并后的有序列表插入任意位置。重复合并直到只剩一个列表。
返回将所有列表合并为一个有序列表所需的最小总成本。
数组的中位数是按非递减顺序排序后的中间元素。如果数组有偶数个元素，中位数是左边的中间元素。
示例 1：
输入：lists = [[1,3,5],[2,4],[6,7,8]]
输出：18
示例 2：
输入：lists = [[1,1,5],[1,4,7,8]]
输出：10
示例 3：
输入：lists = [[1],[3]]
输出：4
示例 4：
输入：lists = [[1],[1]]
输出：2
约束条件：
2 <= lists.length <= 121 <= lists[i].length <= 500-10^9 <= lists[i][j] <= 10^9lists[i]按非递减顺序排序lists[i].length的总和不超过 2000
解题思路
这是一个经典的区间动态规划问题，可以用状态压缩 DP 解决。
核心思路：
- 由于列表数量不超过12，可以使用位掩码表示选择的列表子集
- 预计算所有可能子集对应的合并后列表的中位数
- 使用
dp[mask]表示合并掩码mask中所有列表的最小成本
算法步骤：
- 预处理阶段：对于每个可能的掩码，计算对应列表合并后的结果和中位数
- 状态转移：
dp[mask] = min(dp[s] + dp[mask^s] + cost(s, mask^s))，其中s是mask的非空真子集 - 成本计算：两个子集的合并成本 = 长度之和 + 中位数差的绝对值
优化要点：
- 使用归并排序合并两个已排序的列表
- 预计算所有子集的合并结果避免重复计算
- 只遍历有效的子集分割减少计算量
时间复杂度主要来自于状态数 O(2^n) 和每个状态的转移 O(2^n)，总体为 O(4^n)，在 n≤12 的约束下是可行的。
代码实现
class Solution {
public:
long long minMergeCost(vector<vector<int>>& lists) {
int n = lists.size();
vector<vector<int>> merged(1 << n);
vector<int> medians(1 << n);
// 预计算每个掩码对应的合并结果和中位数
for (int mask = 1; mask < (1 << n); mask++) {
if (__builtin_popcount(mask) == 1) {
int idx = __builtin_ctz(mask);
merged[mask] = lists[idx];
medians[mask] = lists[idx][(lists[idx].size() - 1) / 2];
} else {
// 找到最低位的1
int lowbit = mask & (-mask);
int remaining = mask ^ lowbit;
// 合并两个已排序的列表
vector<int>& a = merged[lowbit];
vector<int>& b = merged[remaining];
vector<int> result;
int i = 0, j = 0;
while (i < a.size() && j < b.size()) {
if (a[i] <= b[j]) {
result.push_back(a[i++]);
} else {
result.push_back(b[j++]);
}
}
while (i < a.size()) result.push_back(a[i++]);
while (j < b.size()) result.push_back(b[j++]);
merged[mask] = result;
medians[mask] = result[(result.size() - 1) / 2];
}
}
// 动态规划
vector<long long> dp(1 << n, LLONG_MAX);
// 初始化单个列表的成本为0
for (int i = 0; i < n; i++) {
dp[1 << i] = 0;
}
for (int mask = 1; mask < (1 << n); mask++) {
if (__builtin_popcount(mask) == 1) continue;
// 枚举所有可能的分割
for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
int complement = mask ^ submask;
if (complement == 0) continue;
long long cost = merged[submask].size() + merged[complement].size() +
abs(medians[submask] - medians[complement]);
if (dp[submask] != LLONG_MAX && dp[complement] != LLONG_MAX) {
dp[mask] = min(dp[mask], dp[submask] + dp[complement] + cost);
}
}
}
return dp[(1 << n) - 1];
}
};
class Solution:
def minMergeCost(self, lists: List[List[int]]) -> int:
n = len(lists)
merged = [[] for _ in range(1 << n)]
medians = [0] * (1 << n)
# 预计算每个掩码对应的合并结果和中位数
for mask in range(1, 1 << n):
if bin(mask).count('1') == 1:
idx = (mask & -mask).bit_length() - 1
merged[mask] = lists[idx][:]
medians[mask] = lists[idx][(len(lists[idx]) - 1) // 2]
else:
# 找到最低位的1
lowbit = mask & (-mask)
remaining = mask ^ lowbit
# 合并两个已排序的列表
a, b = merged[lowbit], merged[remaining]
result = []
i = j = 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
result.append(a[i])
i += 1
else:
result.append(b[j])
j += 1
result.extend(a[i:])
result.extend(b[j:])
merged[mask] = result
medians[mask] = result[(len(result) - 1) // 2]
# 动态规划
dp = [float('inf')] * (1 << n)
# 初始化单个列表的成本为0
for i in range(n):
dp[1 << i] = 0
for mask in range(1, 1 << n):
if bin(mask).count('1') == 1:
continue
# 枚举所有可能的分割
submask = mask
while submask > 0:
complement = mask ^ submask
if complement != 0:
cost = len(merged[submask]) + len(merged[complement]) + abs(medians[submask] - medians[complement])
if dp[submask] != float('inf') and dp[complement] != float('inf'):
dp[mask] = min(dp[mask], dp[submask] + dp[complement] + cost)
submask = (submask - 1) & mask
return dp[(1 << n) - 1]
public class Solution {
public long MinMergeCost(int[][] lists) {
int n = lists.Length;
var merged = new List<int>[1 << n];
var medians = new int[1 << n];
// 预计算每个掩码对应的合并结果和中位数
for (int mask = 1; mask < (1 << n); mask++) {
if (BitOperations.PopCount((uint)mask) == 1) {
int idx = BitOperations.TrailingZeroCount((uint)mask);
merged[mask] = new List<int>(lists[idx]);
medians[mask] = lists[idx][(lists[idx].Length - 1) / 2];
} else {
// 找到最低位的1
int lowbit = mask & (-mask);
int remaining = mask ^ lowbit;
// 合并两个已排序的列表
var a = merged[lowbit];
var b = merged[remaining];
var result = new List<int>();
int i = 0, j = 0;
while (i < a.Count && j < b.Count) {
if (a[i] <= b[j]) {
result.Add(a[i++]);
} else {
result.Add(b[j++]);
}
}
while (i < a.Count) result.Add(a[i++]);
while (j < b.Count) result.Add(b[j++]);
merged[mask] = result;
medians[mask] = result[(result.Count - 1) / 2];
}
}
// 动态规划
var dp = new long[1 << n];
Array.Fill(dp, long.MaxValue);
// 初始化单个列表的成本为0
for (int i = 0; i < n; i++) {
dp[1 << i] = 0;
}
for (int mask = 1; mask < (1 << n); mask++) {
if (BitOperations.PopCount((uint)mask) == 1) continue;
// 枚举所有可能的分割
for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
int complement = mask ^ submask;
if (complement == 0) continue;
long cost = merged[submask].Count + merged[complement].Count +
Math.Abs(medians[submask] - medians[complement]);
if (dp[submask] != long.MaxValue && dp[complement] != long.MaxValue) {
dp[mask] = Math.Min(dp[mask], dp[submask] + dp[complement] + cost);
}
}
}
return dp[(1 << n) - 1];
}
}
/**
* @param {number[][]} lists
* @return {number}
*/
var minMergeCost = function(lists) {
const n = lists.length;
const memo = new Map();
function getMedian(arr) {
return arr[Math.floor((arr.length - 1) / 2)];
}
function mergeTwoLists(a, b) {
const result = [];
let i = 0, j = 0;
while (i < a.length && j < b.length) {
if (a[i] <= b[j]) {
result.push(a[i++]);
} else {
result.push(b[j++]);
}
}
while (i < a.length) result.push(a[i++]);
while (j < b.length) result.push(b[j++]);
return result;
}
function getCost(a, b) {
return a.length + b.length + Math.abs(getMedian(a) - getMedian(b));
}
function solve(currentLists) {
if (currentLists.length === 1) return 0;
const key = JSON.stringify(currentLists.map(list => list.join(',')).sort());
if (memo.has(key)) return memo.get(key);
let minCost = Infinity;
for (let i = 0; i < currentLists.length; i++) {
for (let j = i + 1; j < currentLists.length; j++) {
const cost = getCost(currentLists[i], currentLists[j]);
const merged = mergeTwoLists(currentLists[i], currentLists[j]);
const newLists = [];
for (let k = 0; k < currentLists.length; k++) {
if (k !== i && k !== j) {
newLists.push(currentLists[k]);
}
}
newLists.push(merged);
const totalCost = cost + solve(newLists);
minCost = Math.min(minCost, totalCost);
}
}
memo.set(key, minCost);
return minCost;
}
return solve(lists);
};
复杂度分析
| 复杂度类型 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(4^n × L) | n为列表数量，L为单个列表最大长度。状态数O(2^n)，每个状态转移O(2^n)，合并列表O(L) |
| 空间复杂度 | O(2^n × L) | 存储所有状态的合并结果，每个状态最多包含所有元素 |