這段代碼的時間複雜度是多少（來自leetcode）？

問題是「合併ķ分類鏈接列表，並返回它作爲一個排序列表。」從leetcode 這段代碼的時間複雜度是多少（來自leetcode）？

我的解決方案是使用一個向量，以保持每個鏈表的當前位置，排序該矢量以最小值獲取節點並將其插入到合併列表的末尾。下面是代碼：

bool cmp(ListNode *a, ListNode *b) { 
return a->val < b->val; 
} 
class Solution { 
public: 
ListNode *mergeKLists(vector<ListNode *> &lists) { 
    ListNode *dummy = new ListNode(-1); 
    ListNode *curr = dummy; 

    //init 
    vector<ListNode*> currNodes; 
    for(int i = 0; i < lists.size(); ++i){ 
     if(lists[i] != NULL){ 
      currNodes.push_back(lists[i]); 
     } 
    } 

    while(!currNodes.empty()){ 
     sort(currNodes.begin(), currNodes.end(), cmp); 
     curr->next = currNodes[0]; 
     curr = curr->next; 

     if(currNodes[0]->next != NULL){ 
      currNodes.push_back(currNodes[0]->next); 
     } 
     currNodes.erase(currNodes.begin()); 
    } 

    return dummy->next; 
} 
};

由於性病的時間複雜度::排序是n日誌（n）和我們（N1 + N2 ... NK）的迭代，從而我想總的時間複雜度爲O（（N1 + N2 + ... NK）KLOG（K））。但在每次迭代中，矢量currNodes的大小可能會有所不同，所以我有點困惑。任何人都可以確認嗎？

2. 此外，我看到另一個解決方案在leetcode論壇上使用「合併排序」的思想。它每次都合併兩個鏈表。

public class Solution { 
public ListNode mergeKLists(ArrayList<ListNode> lists) { 
    // IMPORTANT: Please reset any member data you declared, as 
    // the same Solution instance will be reused for each test case. 
    if(lists.isEmpty()) return null; 
    if(lists.size() == 1) return lists.get(0); 
    int k = lists.size(); 
    int log = (int)(Math.log(k)/Math.log(2)); 
    log = log < Math.log(k)/Math.log(2)? log+1:log; // take ceiling 
    for(int i = 1; i <= log; i++){ 
     for(int j = 0; j < lists.size(); j=j+(int)Math.pow(2,i)){ 
      int offset = j+(int)Math.pow(2,i-1); 
      lists.set(j, mergeTwoLists(lists.get(j), (offset >= lists.size()? null : lists.get(offset)))); 
     } 
    } 
    return lists.get(0); 
} 


public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 
    // IMPORTANT: Please reset any member data you declared, as 
    // the same Solution instance will be reused for each test case. 
    if(l1 == null) return l2; 
    if(l2 == null) return l1; 
    ListNode head = l1.val > l2.val? l2:l1; 
    if(head.equals(l2)){ 
     l2 = l1; 
     l1 = head; 
    } 
    while(l1.next != null && l2 != null){ 
     if(l1.next.val > l2.val){ 
      ListNode tmp = l1.next; 
      l1.next = l2; 
      l2 = l2.next; 
      l1 = l1.next; 
      l1.next = tmp; 
     } 
     else 
      l1 = l1.next; 
    } 
    if(l2 != null){ 
     l1.next = l2; 
    } 
    return head; 
} 
}

我想知道這個解決方案的時間複雜度是多少？由於它每次都合併兩個鏈表，所以有log（n）次迭代。但是鏈表在每次迭代之後會變長（因爲它是從兩個鏈表中合併的），如何計算每次迭代的時間複雜度並將它們疊加在一起？

先謝謝您:)

來源

2014-01-16 yvetterowe

這是我的解決方案。複雜度（發現選自K列表1分鐘）*（n個節點）我要說其O（KN），其中k是最佳的解決辦法是O（nlogk）請參見此處列出的數目：How to sort K sorted arrays, with MERGE SORT

但是這只是夠本文給出了已經，所以我沒有做最小堆

// http://oj.leetcode.com/problems/merge-k-sorted-lists/

public ListNode mergeKLists(ArrayList<ListNode> lists) { 
    // Note: The Solution object is instantiated only once and is reused by each test case. 
    ListNode cursor = new ListNode(Integer.MAX_VALUE); 
    ListNode head = cursor; 
    int min = Integer.MAX_VALUE; 
    int index = -1; 
    while(lists.size()>0){ 
     for(int i=0; i<lists.size(); i++){//get 1 min 
      if(lists.get(i)!=null && lists.get(i).val<min){ 
       min = lists.get(i).val; 
       index = i; 
      } 
      if(lists.get(i)==null){ 
       lists.remove(i); 
       i--; 
      } 
     } 
     if(index>=0){//put the min in 
      cursor.next = lists.get(index); 
      cursor = cursor.next; 
      lists.set(index,lists.get(index).next); 
      if(lists.get(index)==null){ 
       lists.remove(index); 
      } 
      min = Integer.MAX_VALUE; 
     } 
    } 
    return head.next; 
}

來源

2014-01-16 04:07:09 Meow

我認爲這是O((n1+n2+n3..nk)logk)解決這個問題，在你以下幾點： -

添加前k個元素到最小堆

除去分鐘元件並從其中包含的分鐘元素列表添加到新列表

刪除下一個元素，並添加到堆。

繼續堆直到空。

更有趣的解決方案： -

使用歸併排序一樣喜歡選擇與哈夫曼編碼合併程序： -

假設有n個元素每個k名單： -

添加所有與大小爲關鍵的列表，以最小堆積

選擇兩個最小的列表並使用合併排序將它們合併爲例程

將新列表添加到堆中，其大小作爲密鑰

1到3直到只剩下一個列表，該列表是您的合併排序列表。

如果有k個列表與n個元素每個然後霍夫曼像合併會給接下來的時間複雜度： -

去除堆兩份清單採用O(logk)

歸併排序像合併需要O(n1+n2)

邏輯迭代在算法： -

合併所有對從尺寸爲N列表ñ服用的n/2 *（N + N）= O（N^2）

合併來自所有對n/2列表大小爲n/4 *（2n + 2n）= O（n^2）...直到O（logK）迭代完成。

時間複雜度：O(n^2*logk)

來源

2014-01-16 04:39:58

這段代碼的時間複雜度是多少（來自leetcode）？

回答

相關問題