BYR Achieve · 镜像论坛

小白求助，分治的时间复杂度

2015/11/30镜像同步1 回复

leetcode上的一道题，Merge k Sorted Lists 使用分治： public class Solution { public ListNode mergeKLists(ListNode[] lists) { int len = lists.length; if(len == 0) return null; if(len == 1) return lists[0]; return mergeLists(0, len - 1, lists); } public ListNode mergeLists(int left, int right, ListNode[] lists){ if(left == right) return lists[left]; if(left + 1 == right) return mergeTwoList(lists[left], lists[right]); int mid = (left + right) / 2; ListNode l1 = mergeLists(left, mid, lists); ListNode l2 = mergeLists(mid + 1, right, lists); return mergeTwoList(l1, l2); } public ListNode mergeTwoList(ListNode l1, ListNode l2){ if(l1 == null) return l2; if(l2 == null) return l1; if(l1.val > l2.val){ ListNode tmp = mergeTwoList(l1, l2.next); l2.next = tmp; return l2; } else{ ListNode tmp = mergeTwoList(l1.next, l2); l1.next = tmp; return l1; } } } 还有直接merge： public class Solution { public ListNode mergeKLists(ListNode[] lists) { int len = lists.length; if(len == 0) return null; if(len == 1) return lists[0]; ListNode l = lists[0]; for(int i = 1; i < len; i++){ l = mergeTwoList(l, lists[i]); } return l; } public ListNode mergeTwoList(ListNode l1, ListNode l2){ if(l1 == null) return l2; if(l2 == null) return l1; if(l1.val > l2.val){ ListNode tmp = mergeTwoList(l1, l2.next); l2.next = tmp; return l2; } else{ ListNode tmp = mergeTwoList(l1.next, l2); l1.next = tmp; return l1; } } } 这两种方法的时间复杂度怎么计算？调用mergeTwoList的次数一样吗？[ema23]

订阅后，新回复会通过你的通知中心匿名送达。