这段代码的时间复杂度是多少（来自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）次迭代。但是链表在每次迭代之后会变长（因为它是从两个链表中合并的），如何计算每次迭代的时间复杂度并将它们叠加在一起？

先谢谢您:)

答

这是我的解决方案。复杂度（发现选自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; 
}

答

我认为这是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)

这段代码的时间复杂度是多少（来自leetcode）？

相关推荐