网站仿站是啥,网站建设亇金手指排名十五,wp网站源码,茶叶网站开发目的和意义输入#xff1a;k个有序链表lists 输出#xff1a;一个有序链表 规则#xff1a;将这个k个有序链表合并成一个有序链表 分析#xff1a;在链表中合并两个有序链表为一个有序链表是基本功。最开始的直觉是我们可以将lists[0]和lists[1]合并得到 result#xff0c;result再和…输入k个有序链表lists 输出一个有序链表 规则将这个k个有序链表合并成一个有序链表 分析在链表中合并两个有序链表为一个有序链表是基本功。最开始的直觉是我们可以将lists[0]和lists[1]合并得到 resultresult再和lists[2]合并一直 到最后合并完成。这个每个节点 都要和其他链表中的一个节点比较所以时间复杂度是O(k*n)。n是所有节点的个数总和。 public ListNode mergeKLists(ListNode[] lists) {ListNode mergeHead new ListNode(0);ListNode node mergeHead;while(true){ListNode minHead null;int idx -1;for (int i0;ilists.length;i) {if (lists[i] ! null) {if(minHead null || minHead.val lists[i].val){minHead lists[i];idx i;}}}if(minHeadnull){break;}lists[idx] lists[idx].next;node.next new ListNode(minHead.val);node node.next;}return mergeHead.next;}分析2可以使用堆排序解决上面的比较问题。在堆中维护的是每个链表 表头元素。移除最小的节点插入链表中的下一个节点。时间复杂度O(nlogk)。 public ListNode mergeKLists(ListNode[] lists) {ListNode dummy new ListNode(-1);ListNode current dummy;PriorityQueueListNode heap new PriorityQueueListNode(new ComparatorListNode(){public int compare(ListNode i1,ListNode i2){return i1.val-i2.val;}});//把头节点放进去for(ListNode node: lists){if(node!null){heap.offer(node);} }while(!heap.isEmpty()){ListNode node heap.poll();if(node.next ! null){heap.offer(node.next);} current.next node;current current.next;}return dummy.next;}分析3使用分治法。先解决lists[0]和lists[1]lists[2]和lists[3]…合并完成只剩下k2\dfrac{k}{2}2k。下一轮解决lists[0]和lists[2]lists[4]和lists[6]…合并完成剩下k4\dfrac{k}{4}4k…一直到最后只剩下lists[0]就是结果。 public ListNode mergeKLists(ListNode[] lists) {for(int interval 1 ;intervallists.length; intervalinterval*2){for(int j 0;jintervallists.length;j j 2*interval){lists[j] mergeTwoLists(lists[j],lists[jinterval]);}}return lists.length0?lists[0]:null;}public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode dummy new ListNode(-1);ListNode currentNode dummy;while(l1!null l2!null){if(l1.val l2.val){currentNode.next l2;l2 l2.next;}else{currentNode.next l1;l1 l1.next;}currentNode currentNode.next;}while(l1!null){currentNode.next l1;l1 l1.next;currentNode currentNode.next;}while(l2!null){currentNode.next l2;l2 l2.next;currentNode currentNode.next;}return dummy.next;}复杂度分析。最外层循环有log2klog_2^klog2k次。mergeTwoLists函数的时间复杂度是n两个列表节点个数的和。最后合起来是O(nlogk)。这里的n是所有链表节点个数和。
