網(wǎng)易首頁 > 網(wǎng)易號 > 正文申請入駐

2026-05-15：合并有序列表的最小成本。用go語言，給定一個二維整數(shù)數(shù)組 lists，其中每個 lists[i] 都是非空且按非遞減順序排列的整數(shù)序列

2026-05-15 00:11:15　來源: moonfdd

北京舉報

分享至

2026-05-15：合并有序列表的最小成本。用go語言，給定一個二維整數(shù)數(shù)組 lists，其中每個 lists[i] 都是非空且按非遞減順序排列的整數(shù)序列。

你可以反復(fù)進(jìn)行操作：每次從 lists 里選出兩個不同的序列 a = lists[i] 和 b = lists[j]，然后把它們合并成一個新序列。該次合并的費用為：

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

其中：len(x) 表示序列長度；median(x) 表示中位數(shù)（先假定序列不變有序，取中間位置；若長度為偶數(shù)，則取左側(cè)中間那個元素）。

進(jìn)行合并后，需要把原來的 a 和 b 從 lists 中移除，并把合并后的有序結(jié)果重新插入到 lists 的任意位置。一直重復(fù)上述操作，直到 lists 中只剩下一個序列。

任務(wù)是：計算把所有子序列最終合并成一個整體有序序列所需的最小總費用，并返回該最小成本。

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 變?yōu)?[[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 變?yōu)?[[1, 2, 3, 4, 5, 6, 7, 8]]，總成本為 6 + 12 = 18。

題目來自力扣3801。

分步詳細(xì)過程+復(fù)雜度分析一、基礎(chǔ)概念鋪墊

1.合并規(guī)則：每次選兩個有序列表合并為新有序列表，費用 = 長度和 + 兩個列表中位數(shù)的絕對差
2.中位數(shù)定義：有序列表，偶數(shù)長度取左側(cè)中間元素，奇數(shù)長度取正中間元素
3.二進(jìn)制掩碼：用一個整數(shù)表示選中的列表子集（如3個列表，掩碼101表示選中第0、2個列表）
4.總目標(biāo)：把所有列表合并為1個，求最小總費用

二、算法整體執(zhí)行步驟（對應(yīng)你的代碼邏輯）第一步：輸入拆分（分治預(yù)處理）

因為列表總數(shù)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]]

第二步：子集合并預(yù)處理（calcSorted函數(shù)）

對前半部分、后半部分分別計算所有子集的合并結(jié)果：

1. 遍歷每一個列表，用二進(jìn)制掩碼標(biāo)記子集
2. 對每一個子集，將其中所有原始列表合并為一個完整的有序數(shù)組
3. 存儲：每個掩碼（子集）對應(yīng) → 該子集合并后的完整有序數(shù)組

具體效果：

? 前半部分（1個列表）：所有子集（共21=2個）都能算出合并后的有序數(shù)組
? 后半部分（2個列表）：所有子集（共22=4個）都能算出合并后的有序數(shù)組
? 作用：后續(xù)任意組合前后子集，都能直接拿到合并后的數(shù)組，不用重復(fù)計算

第三步：所有子集的中位數(shù)預(yù)計算

這是核心優(yōu)化步驟，提前算出任意子集合并后的中位數(shù)，避免DP中重復(fù)計算：

1. 遍歷所有可能的子集掩碼（總共有2?個，n=3時共8個）
2. 把每個掩碼拆分為：前半部分子集 + 后半部分子集
3. 拿到兩部分的合并有序數(shù)組，調(diào)用「尋找兩個正序數(shù)組中位數(shù)」算法
4. 存儲：每個子集掩碼 → 該子集合并后的中位數(shù)

關(guān)鍵意義：

任意兩個子集合并時，它們的中位數(shù)直接查表獲取，極大提升效率。

第四步：狀態(tài)壓縮動態(tài)規(guī)劃（核心求解最小成本）

動態(tài)規(guī)劃定義：

?dp[mask]：將mask代表的所有列表合并為一個數(shù)組的最小總費用
? 目標(biāo)：dp[全1掩碼]（所有列表合并完成的最小成本）

DP執(zhí)行步驟：

1.初始化

? 單個列表的掩碼（如001/010/100）：無需合并，費用為0
? 其余掩碼初始化為無窮大（表示暫未計算）

2.遍歷所有子集掩碼
從小到大遍歷所有掩碼，保證計算大子集時，其子集已經(jīng)算完：

? 跳過單個列表的掩碼
? 對當(dāng)前掩碼，拆分所有合法的兩個不相交子集（j和k，j+k=當(dāng)前掩碼）
? 計算合并這兩個子集的費用：dp[j] + dp[k] + 合并費用
? 合并費用公式：子集j長度 + 子集k長度 + |j的中位數(shù) - k的中位數(shù)|
? 更新dp[mask]為所有拆分方式中的最小值

3.最終結(jié)果
全1掩碼（所有列表合并）對應(yīng)的dp值，就是最小總費用。

第五步：示例驗證（對應(yīng)題目輸入輸出）

輸入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，與算法計算結(jié)果一致。

三、時間復(fù)雜度分析

我們基于核心參數(shù)計算：

? n：列表總數(shù)（≤12）
? L：所有列表總長度（≤2000）

1. 子集合并預(yù)處理

? 總子集數(shù)：2?（n≤12 → 4096）
? 每個子集合并：總長度O(L)
? 時間：O(2? × L)

2. 中位數(shù)預(yù)計算

? 總子集數(shù)：2?
? 每個中位數(shù)計算：O(logL)
? 時間：O(2? × logL)

3. 動態(tài)規(guī)劃核心

? 總掩碼數(shù)：2?
? 每個掩碼拆分：O(3?)（子集拆分的經(jīng)典復(fù)雜度）
? 單次計算：O(1)（查表）
? 時間：O(3?)

總時間復(fù)雜度

O(2? × L + 3?)

? n≤12時：312=531441，212×2000=800萬，計算量極小，完全滿足要求。

四、額外空間復(fù)雜度（除輸入外的占用空間） 1. 存儲子集合并數(shù)組

? 總子集數(shù)：2?
? 每個子集存儲合并后的數(shù)組：總空間O(L)
? 空間：O(2? + L)

2. 存儲中位數(shù)、DP數(shù)組

? 中位數(shù)數(shù)組：O(2?)
? DP數(shù)組：O(2?)

總額外空間復(fù)雜度

O(2? + L)

? 212=4096，L≤2000，空間占用極低。

總結(jié)

1.核心思路：利用狀態(tài)壓縮DP解決小規(guī)模（n≤12）的合并最優(yōu)解問題，通過分治預(yù)處理+子集預(yù)計算優(yōu)化效率；
2.執(zhí)行流程：拆分列表→預(yù)處理所有子集合并結(jié)果→預(yù)計算所有子集中位數(shù)→DP枚舉所有合并方式求最小成本；
3.復(fù)雜度：

? 時間：O(2?×總長度 + 3?)，n≤12時效率極高；
? 額外空間：O(2? + 總長度)，空間占用極小。

Go完整代碼如下：

package main

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

 // 88. 合并兩個有序數(shù)組（創(chuàng)建一個新數(shù)組）
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. 尋找兩個正序數(shù)組的中位數(shù)
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 中找合并后的數(shù)組 
 
 
          
 // 高 n-half 位去 sorted2 中找合并后的數(shù)組 
 
 
         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. 合并兩個有序數(shù)組（創(chuàng)建一個新數(shù)組）"""
    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]]:
    """預(yù)計算所有子集合并后的有序數(shù)組"""
    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. 尋找兩個正序數(shù)組的中位數(shù)（這里返回較大的那半）"""
    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. 合并兩個有序數(shù)組（創(chuàng)建一個新數(shù)組）
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++;
        }
    }
}

 // 預(yù)計算所有子集合并后的有序數(shù)組
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. 尋找兩個正序數(shù)組的中位數(shù)（這里返回較大的那半） 
 
 
 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科普文章、工具評測、提升效率的秘籍以及行業(yè)洞察。歡迎關(guān)注“福大大架構(gòu)師每日一題”，發(fā)消息可獲得面試資料，讓AI助力您的未來發(fā)展。

特別聲明：以上內(nèi)容(如有圖片或視頻亦包括在內(nèi))為自媒體平臺“網(wǎng)易號”用戶上傳并發(fā)布，本平臺僅提供信息存儲服務(wù)。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.