转载

面试题:如何来判断一个List是否有序?

前语: 不要为了读文章而读文章,一定要带着问题来读文章,勤思考。

这是一位同学面试的过程中遇到的面试题,我觉得挺有意思,去研究了一下,发现竟然有这么多方法,在此,与大家分享一下。

关于List这种数据结构,在这里我就不多说了,很重要,不知道的同学可以翻阅以前的文章。

对于这类问题,你首先要给面试官一个定心丸: List是java.util.Collection 接口的一个子接口,并且是一个有序列表 这一步很关键,不能错,一定要记清楚,如果这一步错,那么后面说再多,也等于零,请记住下面这张图。

面试题:如何来判断一个List是否有序?

我们再来抓这个问题的关键点: 如何用程序证明List是有序的?

方法即是迭代List并比较相邻元素。 如果两个相邻元素中的任何一个未排序,我们可以说List未排序。

下面我就来列举几种方法。

1、迭代器

其实Java的遍历有三种方式: for、foreach、Iterator; 关于这三种的区别,你也可以在面试中延伸一下(比如说 为什么在Iterator能够修改集合内部的元素,而foreach不行? 会抛什么异常? )。

既然提到遍历,那么这里有有两个东东需要提一下Comparator与Comparable,它们的区别是什么?

Comparable 如果一个类实现了该接口,那么该类默认支持排序,相当于“ 内部比较器 ”。

Comparator 如果一个类型实现该接口,那么该类自身不支持排序,它只是充当一个“ 外部比较器 ”的角色。

以String为例,它自身实现了 Comparable接口,那么我可以用下面这种方式来验证:


 

public static boolean isSorted(List<String> listOfStrings) {

if (isEmpty(listOfStrings) || listOfStrings.size() == 1) {

return true;

}

Iterator<String> iter = listOfStrings.iterator();

String current, previous = iter.next();

while (iter.hasNext()) {

current = iter.next();

if (previous.compareTo(current) > 0) {

return false;

}

previous = current;

}

return true;

}

我们自己建的类一般不会自动实现 Comparable接口,那么我们可以尝试用 Comparator来进行比较,如:


 

public static boolean isSorted(List<Employee> employees, Comparator<Employee> employeeComparator) {

if (isEmpty(employees) || employees.size() == 1) {

return true;

}

Iterator<Employee> iter = employees.iterator();

Employee current, previous = iter.next();

while (iter.hasNext()) {

current = iter.next();

if (employeeComparator.compare(previous, current) > 0) {

return false;

}

previous = current;

}

return true;

}

通过上面的例子,我们可以发现不同之处: 在于前后两个元素的比较方式上。 总得来说,如果你建的类默认有排序功能,那么建议用Comparable; 但是,我们可以使用Comparator进行精确控制排序。

到这里,看出来没,一个迭代器咱们就可以吹这么多牛皮出来^_^

2、递归

递归这种方式只是一种思路,我觉得用的比较巧妙,啥都不说了,直接上代码。


 

public static boolean isSorted(List<String> listOfStrings) {

return isSorted(listOfStrings, listOfStrings.size());

}

public static boolean isSorted(List<String> listOfStrings, int index) {

if (index < 2) {

return true;

} else if (listOfStrings.get(index - 2).compareTo(listOfStrings.get(index - 1)) > 0) {

return false;

} else {

return isSorted(listOfStrings, index - 1);

}

}

说实话,这种证明操作我刚开始是没有想到的,很巧妙的玩法。

3、第三方组件

这里就不得不提谷歌开源的 Guava ,这个组件基本上包含了我们常用的所有工具类,也包括检验排序。

比如,利用Guava的Ordering类检查List是否有序,同样它也提供了两种方式,一种是针对于实现了Comparable接口的类型,比如:


 

public static boolean isSorted(List<String> listOfStrings) {

return Ordering.<String> natural().isOrdered(listOfStrings);

}

另一种是使用 Comparator进行排序的类,比如:


 

public static boolean isSorted(List<Employee> employees, Comparator<Employee> employeeComparator) {

return Ordering.from(employeeComparator).isOrdered(employees);

}

它内部还有很多方法,比如natural().reverseOrder():来检查列表是否按相反的顺序排序; 再比如我们可以使用natural().nullFirst()和natural().nullLast()来检查null是否出现在排序列表的第一个或最后一个。

如果我们使用Java 8及以上的版本,Guava在Comparators类方面提供了更好的选择,比如以下示例:


 

public static boolean isSorted(List<String> listOfStrings) {

return Comparators.isInOrder(listOfStrings, Comparator.<String> naturalOrder());

}

从上面的示例中,使用默认顺序来检查排序列表,但我们也可以使用Comparator来自定义排序检查。

小结

从本文,我们可以看出,面试的过程中,首先要抓住问题的关键点,然后把自己知道的知识点一点点延展开来,让面试官知道你的深度与广度,就比如我昨天发的这篇关于浮点数科学计数法的文章《 Stackoverflow: 为什么将0.1f改为0会使性能降低10倍? 》,浮点数这个知识点基础吗? 确实基础,基础到大多数程序员而不屑一看! 重要吗? 真重要,稍不注意就会出错,比如下面这种写法:


 

if(0.9f-0.8f == 0.1f){

System.err.println("equal");

}else {

System.err.println("no equal");

}

特别像我们做金融的,线上出现这种问题就有可能是致命的; 比如我们公司金额全部都用整数,不做浮点数计算,容易损失精度,要么用BigDecimal。 所以,我也一直强调基础很重要,比如算法,虽然你工作中用到的很少,但你得知道那几种基本算法,什么样的数据量该选谁最优,正如孤尽大佬所说的“ 一个方法看起来数据量没多少,没必要进行算法优化,但是乘以一个访问量级,那么它对服务器的性能损耗将是巨大的! ”等等。

还有我每次分享给大家的文章,真值得你仔细去研究,每篇文章的内容不能保证百分之百的不出错,但每篇文章引申出来的知识点,就值得你去延伸,自己不动手,又想成为大牛,别做梦了!

真的,编程这条道路上,只能靠自己,谁也帮不了你!

THE END

面试题:如何来判断一个List是否有序?

下方查看 历史 文章

Java 8的这个新特性,你用了吗?

ThreadLocal:Java中的影分身

可能是最全面的G1学习笔记

Java面试题-基础知识

你再主动一点点    我们就有故事了

本号专注于后端技术、JVM问题排查和优化、Java面试题、个人成长和自我管理等主题,为读者提供一线开发者的工作和成长经验,期待你能在这里有所收获。关注后,记得回复关键词获取独家技术资料哦。

面试题:如何来判断一个List是否有序?

让我知道你“在看”

面试题:如何来判断一个List是否有序?

原文  http://mp.weixin.qq.com/s?__biz=MzIwMjA3MDE3MQ==&mid=2650737960&idx=1&sn=551f0e0a2ee756048e80f107e498eaf5
正文到此结束
Loading...