使用Java中Comparator接口实现自定义排序
一般情况下,自己动手写一个简单排序程序还是没有问题的,但是你能保证写出来的排序程序的时间复杂度吗?你能保证程序的正确性吗,鲁棒性呢,还有程序结构的清晰性,可维护性.......综上所述,学习一下排序接口来实现对复杂对象的排序还是很有必要的。Java中有两个用来实现排序的接口Comparator和Comparable接口,本人比较喜欢使用java的Comparator接口,在程序里实现Comparator接口里的compare(Object o1,Object o2)方法,然后在程序中通过调用Arrays.sort(array,new DemoClass())或者Collections.sort(collection,new DemoClass())来实现对对象数组的排序,直接上一栗子:
描述:
Merge k sorted
linked lists and return it as one sorted list. Analyze and describe its complexity.
思路:
本来想模仿合并两个链表的方法,查找所有的lists链表一遍找出一个最小值,并将最小值链接到结果链表中,并将最小结点删除,将最小结点的next结点替代之,直至为null,将链表删去。
但是当lists.size()比较大时,时间复杂度就上来了,而且每次只能选一个最小结点,O(N*N)的节奏。。。
所以,想到不就是排序么,将所有的结点集合到一起,然后对其进行快速排序不就可以了么,啊哈,真的是这样,bravo!
很显然,这种方法肯定不是最优方法,但是时间复杂度也只是O(N*logN),也是可以接受的。
代码:
public class Solution implements Comparator<ListNode> { public int compare(ListNode t1, ListNode t2) { return t1.val - t2.val; } public ListNode mergeKLists(List<ListNode> lists) { if (lists == null || lists.size() == 0) return null; if (lists.size() == 1)// just have one linkedlist return lists.get(0); int i=0,len=0; List<ListNode> returnList = new ArrayList<ListNode>(); ListNode cur = null; for (i = 0; i < lists.size(); i++) { cur = lists.get(i); while (cur != null) { returnList.add(cur); cur = cur.next; } } Collections.sort(returnList, new Solution()); ListNode pre = returnList.get(0); cur = null; len = returnList.size(); for (i = 1; i < len; i++) { cur = returnList.get(i); pre.next = cur; pre = cur; } returnList.get(len - 1).next = null; return returnList.get(0); } }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。