分治算法+题目

分治算法+题目 分治算法是什么题目：合并K个升序链表总结

分治算法是什么

把问题分解后进行求解，相比于不分解直接求解，时间复杂度更低。符合这个特征的算法，我们才称之为「分治算法」。

题目：合并K个升序链表

题目 分治算法：

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { //分治的思想 二分分治 时间复杂度是O(N*logN) public ListNode mergeKLists(ListNode[] lists) { int sz=lists.length; return merge(lists,0,sz-1); } //定义:合并lists[startIndex...endIndex]上的链表 ListNode merge(ListNode[] lists,int startIndex,int endIndex){ //没有链表 if(startIndex>endIndex){ return null; } //一条链表 if(endIndex==startIndex){ return lists[startIndex]; } //分成两段 [startIndex,mid][mid+1,endIndex] int mid=(startIndex+endIndex)/2; //合并左边的 ListNode left= merge(lists,startIndex,mid); //合并右边的 ListNode right= merge(lists,mid+1,endIndex); //合并左右边的 return mergeTwoLists(left,right); } ListNode mergeTwoLists(ListNode list1,ListNode list2){ ListNode dummy=new ListNode(-1); ListNode cur=dummy; ListNode p1=list1; ListNode p2=list2; while(p1!=null && p2!=null){ if(p1.val<p2.val){ cur.next=p1; p1=p1.next; }else{ cur.next=p2; p2=p2.next; } cur=cur.next; } while(p1!=null ){ cur.next=p1; p1=p1.next; cur=cur.next; } while(p2!=null ){ cur.next=p2; p2=p2.next; cur=cur.next; } cur.next=null; return dummy.next; } }

优先级队列：

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { //把所有的节点放入 优先级队列中 然后一个个取出 public ListNode mergeKLists(ListNode[] lists) { // 优先级队列，最小堆 PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() { @Override public int compare(ListNode o1, ListNode o2) { // TODO Auto-generated method stub return o1.val-o2.val; } }); //取出所有链表 将每个节点入队列 for(ListNode list:lists) { ListNode cur=list; while(cur!=null) { pq.add(cur); cur=cur.next; } } //取出所有节点 ListNode dummy=new ListNode(-1),cur=dummy; while(!pq.isEmpty()) { cur.next=pq.poll(); cur=cur.next; } cur.next=null; return dummy.next; } } 总结

把递归算法抽象成递归树，如果递归树节点的时间复杂度和树的深度相关，那么使用分治思想对问题进行二分，就可以使递归树尽可能平衡，进而优化总的时间复杂度。