2026-05-15：合并有序列表的最小成本。用go语言，给定一个二维整数数组 lists，其中每个 lists[i] 都是非空且按非递减顺序排列的整数序列

2026-05-15：合并有序列表的最小成本。用go语言，给定一个二维整数数组 lists，其中每个 lists[i] 都是非空且按非递减顺序排列的整数序列。

你可以反复进行操作：每次从 lists 里选出两个不同的序列 a = lists[i] 和 b = lists[j]，然后把它们合并成一个新序列。该次合并的费用为：

len(a) + len(b) + abs(median(a) – median(b))

其中：len(x) 表示序列长度；median(x) 表示中位数（先假定序列不变有序，取中间位置；若长度为偶数，则取左侧中间那个元素）。

进行合并后，需要把原来的 a 和 b 从 lists 中移除，并把合并后的有序结果重新插入到 lists 的任意位置。一直重复上述操作，直到 lists 中只剩下一个序列。

任务是：计算把所有子序列最终合并成一个整体有序序列所需的最小总费用，并返回该最小成本。

2 <= lists.length <= 12。

1 <= lists[i].length <= 500。

-1000000000 <= lists[i][j] <= 1000000000。

lists[i] 按照非递减顺序排序。

lists[i].length 的总和不超过 2000。

输入: lists = [[1,3,5],[2,4],[6,7,8]]。

输出: 18。

解释:

合并 a = [1, 3, 5] 和 b = [2, 4]：

len(a) = 3，len(b) = 2

median(a) = 3，median(b) = 2

cost = len(a) + len(b) + abs(median(a) – median(b)) = 3 + 2 + abs(3 – 2) = 6

此时 lists 变为 [[1, 2, 3, 4, 5], [6, 7, 8]]。

合并 a = [1, 2, 3, 4, 5] 和 b = [6, 7, 8]：

len(a) = 5，len(b) = 3

median(a) = 3，median(b) = 7

cost = len(a) + len(b) + abs(median(a) – median(b)) = 5 + 3 + abs(3 – 7) = 12

此时 lists 变为 [[1, 2, 3, 4, 5, 6, 7, 8]]，总成本为 6 + 12 = 18。

题目来自力扣3801。

分步详细过程+复杂度分析 一、基础概念铺垫

1.合并规则：每次选两个有序列表合并为新有序列表，费用 = 长度和 + 两个列表中位数的绝对差

2.中位数定义：有序列表，偶数长度取左侧中间元素，奇数长度取正中间元素

3.二进制掩码：用一个整数表示选中的列表子集（如3个列表，掩码101表示选中第0、2个列表）

4.总目标：把所有列表合并为1个，求最小总费用

二、算法整体执行步骤（对应你的代码逻辑） 第一步：输入拆分（分治预处理）

因为列表总数n≤12，直接全量计算效率低，代码将所有列表平分为前后两半：

• 示例输入：[[1,3,5],[2,4],[6,7,8]]，n=3

• 前半部分m=1个列表：[[1,3,5]]

• 后半部分n-m=2个列表：[[2,4],[6,7,8]]

第二步：子集合并预处理（calcSorted函数）

对前半部分、后半部分分别计算所有子集的合并结果：

1. 遍历每一个列表，用二进制掩码标记子集

2. 对每一个子集，将其中所有原始列表合并为一个完整的有序数组

3. 存储：每个掩码（子集）对应 → 该子集合并后的完整有序数组

具体效果：

• 前半部分（1个列表）：所有子集（共2¹=2个）都能算出合并后的有序数组

• 后半部分（2个列表）：所有子集（共2²=4个）都能算出合并后的有序数组

• 作用：后续任意组合前后子集，都能直接拿到合并后的数组，不用重复计算

第三步：所有子集的中位数预计算

这是核心优化步骤，提前算出任意子集合并后的中位数，避免DP中重复计算：

1. 遍历所有可能的子集掩码（总共有2ⁿ个，n=3时共8个）

2. 把每个掩码拆分为：前半部分子集 + 后半部分子集

3. 拿到两部分的合并有序数组，调用「寻找两个正序数组中位数」算法

4. 存储：每个子集掩码 → 该子集合并后的中位数

关键意义：

任意两个子集合并时，它们的中位数直接查表获取，极大提升效率。

第四步：状态压缩动态规划（核心求解最小成本）

动态规划定义：

•dp[mask]：将mask代表的所有列表合并为一个数组的最小总费用

• 目标：dp[全1掩码]（所有列表合并完成的最小成本）

DP执行步骤：

1.初始化

• 单个列表的掩码（如001/010/100）：无需合并，费用为0

• 其余掩码初始化为无穷大（表示暂未计算）

2.遍历所有子集掩码
从小到大遍历所有掩码，保证计算大子集时，其子集已经算完：

• 跳过单个列表的掩码

• 对当前掩码，拆分所有合法的两个不相交子集（j和k，j+k=当前掩码）

• 计算合并这两个子集的费用：dp[j] + dp[k] + 合并费用

• 合并费用公式：子集j长度 + 子集k长度 + |j的中位数 - k的中位数|

• 更新dp[mask]为所有拆分方式中的最小值

3.最终结果
全1掩码（所有列表合并）对应的dp值，就是最小总费用。

第五步：示例验证（对应题目输入输出）

输入3个列表：A[1,3,5]、B[2,4]、C[6,7,8]

1. 合并A+B：费用=3+2+|3-2|=6

2. 合并(AB)+C：费用=5+3+|3-7|=12

3. 总费用=6+12=18，与算法计算结果一致。

三、时间复杂度分析

我们基于核心参数计算：

• n：列表总数（≤12）

• L：所有列表总长度（≤2000）

1. 子集合并预处理

• 总子集数：2ⁿ（n≤12 → 4096）

• 每个子集合并：总长度O(L)

• 时间：O(2ⁿ × L)

2. 中位数预计算

• 总子集数：2ⁿ

• 每个中位数计算：O(logL)

• 时间：O(2ⁿ × logL)

3. 动态规划核心

• 总掩码数：2ⁿ

• 每个掩码拆分：O(3ⁿ)（子集拆分的经典复杂度）

• 单次计算：O(1)（查表）

• 时间：O(3ⁿ)

总时间复杂度

O(2ⁿ × L + 3ⁿ)

• n≤12时：3¹²=531441，2¹²×2000=800万，计算量极小，完全满足要求。

四、额外空间复杂度（除输入外的占用空间） 1. 存储子集合并数组

• 总子集数：2ⁿ

• 每个子集存储合并后的数组：总空间O(L)

• 空间：O(2ⁿ + L)

2. 存储中位数、DP数组

• 中位数数组：O(2ⁿ)

• DP数组：O(2ⁿ)

总额外空间复杂度

O(2ⁿ + L)

• 2¹²=4096，L≤2000，空间占用极低。

总结

1.核心思路：利用状态压缩DP解决小规模（n≤12）的合并最优解问题，通过分治预处理+子集预计算优化效率；

2.执行流程：拆分列表→预处理所有子集合并结果→预计算所有子集中位数→DP枚举所有合并方式求最小成本；

3.复杂度：

• 时间：O(2ⁿ×总长度 + 3ⁿ)，n≤12时效率极高；

• 额外空间：O(2ⁿ + 总长度)，空间占用极小。

Go完整代码如下：

package main

 import (
    "fmt"
    "math"
    "sort"
)

 // 88. 合并两个有序数组（创建一个新数组）
func merge(a, b []int) []int {
    i, n := 0, len(a)
    j, m := 0, len(b)
    res := make([]int, 0, n+m)
    for {
        if i == n {
            returnappend(res, b[j:]...)
        }
        if j == m {
            returnappend(res, a[i:]...)
        }
        if a[i] < b[j] {
            res = append(res, a[i])
            i++
        } else {
            res = append(res, b[j])
            j++
        }
    }
}

 func calcSorted(lists [][]int) [][]int {
    u := 1 << len(lists)
    sorted := make([][]int, u)
    for i, a := range lists {
        highBit := 1 << i
        for s, b := range sorted[:highBit] {
            sorted[highBit|s] = merge(a, b)
        }
    }
    return sorted
}

 // 4. 寻找两个正序数组的中位数
func findMedianSortedArrays(a, b []int)int {
    iflen(a) > len(b) {
        a, b = b, a
    }

     m, n := len(a), len(b)
    i := sort.Search(m, func(i int)bool {
        j := (m+n+1)/2 - i - 2
        return a[i] > b[j+1]
    }) - 1

     j := (m+n+1)/2 - i - 2
    if i < 0 {
        return b[j]
    }
    if j < 0 {
        return a[i]
    }
    return max(a[i], b[j])
}

 func minMergeCost(lists [][]int)int64 {
    n := len(lists)
    m := n / 2
    sorted1 := calcSorted(lists[:m])
    sorted2 := calcSorted(lists[m:])

     u := 1 << n
    half := 1< 
 
 1 
 
 
     median :=  
 make 
 ([] 
 int 
 , u) 
 
 
      
 for 
  i :=  
 1 
 ; i < u; i++ { 
 
 
          
 // 把 i 分成低 m 位和高 n-m 位 
 
 
          
 // 低 half 位去 sorted1 中找合并后的数组 
 
 
          
 // 高 n-half 位去 sorted2 中找合并后的数组 
 
 
         median[i] = findMedianSortedArrays(sorted1[i&half], sorted2[i>>m]) 
 
 
     } 
 
 
 
 
     f :=  
 make 
 ([] 
 int 
 , u) 
 
 
      
 for 
  i :=  
 range 
  f { 
 
 
          
 if 
  i&(i 
 -1 
 ) ==  
 0 
  { 
 
 
              
 continue 
 
 
         } 
 
 
         f[i] = math.MaxInt 
 
 
          
 for 
  j := i & (i -  
 1 
 ); j > i^j; j = (j -  
 1 
 ) & i { 
 
 
             k := i ^ j 
 
 
             f[i] = min(f[i], f[j]+f[k]+abs(median[j]-median[k])) 
 
 
         } 
 
 
         f[i] +=  
 len 
 (sorted1[i&half]) +  
 len 
 (sorted2[i>>m]) 
 
 
     } 
 
 
      
 return 
 int64 
 (f[u 
 -1 
 ]) 
 
 
 } 
 
 
 
 
 func abs(x int) 
 int 
  { 
 
 
      
 if 
  x <  
 0 
  { 
 
 
          
 return 
  -x 
 
 
     } 
 
 
      
 return 
  x 
 
 
 } 
 
 
 
 
 func main() 
  { 
 
 
     lists := [][] 
 int 
 {{ 
 1 
 ,  
 3 
 ,  
 5 
 }, { 
 2 
 ,  
 4 
 }, { 
 6 
 ,  
 7 
 ,  
 8 
 }} 
 
 
     result := minMergeCost(lists) 
 
 
     fmt.Println(result) 
 
 
 } 
 
 
 

Python完整代码如下：

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

 from typing import List

 def merge(a: List[int], b: List[int]) -> List[int]:
    """88. 合并两个有序数组（创建一个新数组）"""
    i, n = 0, len(a)
    j, m = 0, len(b)
    res = []
    while True:
        if i == n:
            res.extend(b[j:])
            return res
        if j == m:
            res.extend(a[i:])
            return res
        if a[i] < b[j]:
            res.append(a[i])
            i += 1
        else:
            res.append(b[j])
            j += 1

 def calc_sorted(lists: List[List[int]]) -> List[List[int]]:
    """预计算所有子集合并后的有序数组"""
    u = 1 << len(lists)
    sorted_arr = [[] for _ in range(u)]
    for i, a in enumerate(lists):
        high_bit = 1 << i
        for s in range(high_bit):
            sorted_arr[high_bit | s] = merge(a, sorted_arr[s])
    return sorted_arr

 def find_median_sorted_arrays(a: List[int], b: List[int]) -> int:
    """4. 寻找两个正序数组的中位数（这里返回较大的那半）"""
    iflen(a) > len(b):
        a, b = b, a
    m, n = len(a), len(b)
    # 二分查找 i
    left, right = 0, m
    while left < right:
        mid = (left + right) // 2
        j = (m + n + 1) // 2 - mid - 2
        if j + 1 < n and a[mid] > b[j + 1]:
            right = mid
        else:
            left = mid + 1
    i = left - 1
    j = (m + n + 1) // 2 - i - 2
    if i < 0:
        return b[j]
    if j < 0:
        return a[i]
    return max(a[i], b[j])

 def min_merge_cost(lists: List[List[int]]) -> int:
    """计算最小合并代价"""
    n = len(lists)
    m = n // 2
    sorted1 = calc_sorted(lists[:m])
    sorted2 = calc_sorted(lists[m:])
    u = 1 << n
    half = (1 << m) - 1
    median = [0] * u
    for i in range(1, u):
        median[i] = find_median_sorted_arrays(
            sorted1[i & half],
            sorted2[i >> m]
        )
    f = [0] * u
    INF = float('inf')
    for i in range(u):
        if i & (i - 1) == 0:
            continue
        f[i] = INF
        j = i & (i - 1)
        while j > (i ^ j):
            k = i ^ j
            f[i] = min(f[i], f[j] + f[k] + abs(median[j] - median[k]))
            j = (j - 1) & i
        f[i] += len(sorted1[i & half]) + len(sorted2[i >> m])
    return f[u - 1]

 def main():
    lists = [[1, 3, 5], [2, 4], [6, 7, 8]]
    result = min_merge_cost(lists)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代码如下：

  

  

   

  


 using namespace std;

 // 88. 合并两个有序数组（创建一个新数组）
vector merge(const vector& a, const vector& b) {
    int i = 0, n = a.size();
    int j = 0, m = b.size();
    vector res;
    res.reserve(n + m);

     while (true) {
        if (i == n) {
            res.insert(res.end(), b.begin() + j, b.end());
            return res;
        }
        if (j == m) {
            res.insert(res.end(), a.begin() + i, a.end());
            return res;
        }
        if (a[i] < b[j]) {
            res.push_back(a[i]);
            i++;
        } else {
            res.push_back(b[j]);
            j++;
        }
    }
}

 // 预计算所有子集合并后的有序数组
vector 
 
 int 
 >> calcSorted( 
 const 
  vector 
 
 int 
 >>& lists) { 
 
 
      
 int 
  u =  
 1 
  << lists.size(); 
 
 
     vector 
 
 int 
 >> sorted(u); 
 
 
 
 
      
 for 
  ( 
 int 
  i =  
 0 
 ; i < lists.size(); i++) { 
 
 
          
 int 
  highBit =  
 1 
  << i; 
 
 
          
 for 
  ( 
 int 
  s =  
 0 
 ; s < highBit; s++) { 
 
 
             sorted[highBit | s] = merge(lists[i], sorted[s]); 
 
 
         } 
 
 
     } 
 
 
 
 
      
 return 
  sorted; 
 
 
 } 
 
 
 
 
 // 4. 寻找两个正序数组的中位数（这里返回较大的那半） 
 
 
 int 
  findMedianSortedArrays(vector< 
 int 
 > a, vector< 
 int 
 > b) { 
 
 
      
 if 
  (a.size() > b.size()) { 
 
 
         swap(a, b); 
 
 
     } 
 
 
 
 
      
 int 
  m = a.size(), n = b.size(); 
 
 
 
 
      
 // 二分查找 i（等价于 Go 的 sort.Search） 
 
 
      
 int 
  left =  
 0 
 , right = m; 
 
 
     while (left < right) { 
 
 
          
 int 
  mid = (left + right) /  
 2 
 ; 
 
 
          
 int 
  j = (m + n +  
 1 
 ) /  
 2 
  - mid -  
 2 
 ; 
 
 
          
 if 
  (j +  
 1 
  < n && a[mid] > b[j +  
 1 
 ]) { 
 
 
             right = mid; 
 
 
         }  
 else 
  { 
 
 
             left = mid +  
 1 
 ; 
 
 
         } 
 
 
     } 
 
 
 
 
      
 int 
  i = left -  
 1 
 ; 
 
 
      
 int 
  j = (m + n +  
 1 
 ) /  
 2 
  - i -  
 2 
 ; 
 
 
 
 
      
 if 
  (i <  
 0 
 )  
 return 
  b[j]; 
 
 
      
 if 
  (j <  
 0 
 )  
 return 
  a[i]; 
 
 
      
 return 
  max(a[i], b[j]); 
 
 
 } 
 
 
 
 
 // 计算最小合并代价 
 
 
 long long minMergeCost( 
 const 
  vector 
 
 int 
 >>& lists) { 
 
 
      
 int 
  n = lists.size(); 
 
 
      
 int 
  m = n /  
 2 
 ; 
 
 
 
 
     vector 
 
 int 
 >> sorted1 = calcSorted( 
 
 
         vector 
 
 int 
 >>(lists.begin(), lists.begin() + m) 
 
 
         ); 
 
 
     vector 
 
 int 
 >> sorted2 = calcSorted( 
 
 
         vector 
 
 int 
 >>(lists.begin() + m, lists.end()) 
 
 
         ); 
 
 
 
 
      
 int 
  u =  
 1 
  << n; 
 
 
      
 int 
  half = ( 
 1 
  << m) -  
 1 
 ; 
 
 
 
 
     vector< 
 int 
 > median(u); 
 
 
      
 for 
  ( 
 int 
  i =  
 1 
 ; i < u; i++) { 
 
 
         median[i] = findMedianSortedArrays( 
 
 
             sorted1[i & half], 
 
 
             sorted2[i >> m] 
 
 
             ); 
 
 
     } 
 
 
 
 
     vector 
 
 f(u,  
 
 0 
 ); 
 
 
      
 for 
  ( 
 int 
  i =  
 0 
 ; i < u; i++) { 
 
 
          
 if 
  ((i & (i -  
 1 
 )) ==  
 0 
 ) { 
 
 
              
 continue 
 ; 
 
 
         } 
 
 
         f[i] = LLONG_MAX; 
 
 
          
 for 
  ( 
 int 
  j = i & (i -  
 1 
 ); j > (i ^ j); j = (j -  
 1 
 ) & i) { 
 
 
              
 int 
  k = i ^ j; 
 
 
             f[i] = min(f[i], f[j] + f[k] + abs(median[j] - median[k])); 
 
 
         } 
 
 
         f[i] += sorted1[i & half].size() + sorted2[i >> m].size(); 
 
 
     } 
 
 
 
 
      
 return 
  f[u -  
 1 
 ]; 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
     vector 
 
 int 
 >> lists = {{ 
 1 
 ,  
 3 
 ,  
 5 
 }, { 
 2 
 ,  
 4 
 }, { 
 6 
 ,  
 7 
 ,  
 8 
 }}; 
 
 
     long long result = minMergeCost(lists); 
 
 
     cout << result << endl; 
 
 
      
 return 
 0 
 ; 
 
 
 } 
 
 
 
 
 
 
 
 
 
 
 

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。