Java 高效检查一个数组中是否包含某个值
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Java 高效检查一个数组中是否包含某个值,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2998字,纯文字阅读大概需要5分钟。
内容图文
如何检查一个数组(未排序)中是否包含某个特定的值?在Java中,这是一个非常有用并又很常用的操作。同时,在StackOverflow中,有时一个得票非常高的问题。在得票比较高的几个回答中,时间复杂度差别也很大。
1、不同的实现方式
使用list
1 public static boolean useList(String[] arr, String targetValue) { 2 return Arrays.asList(arr).contains(targetValue); 3 }
使用set
1 public static boolean useSet(String[] arr, String targetValue) { 2 Set<String> set = new HashSet<String>(Arrays.asList(arr)); 3return set.contains(targetValue); 4 }
使用循环
1 public static boolean useLoop(String[] arr, String targetValue) { 2 for (String s : arr) { 3 if (s.equals(targetValue)) { 4 return true ; 5 } 6 } 7 return false ; 8 }
使用Arrays.binarySearch
此法为二分搜索法,故查询前需要用sort()方法将数组排序,如果数组没有排序,则结果是不确定的,另外
如果数组中含有多个指定值的元素,则无法保证找到的是哪一个。
1 public static boolean useArraysBinarySearch(String[] arr, String targetValue) { 2 int a = Arrays.binarySearch(arr, targetValue); 3if (a > 0) { 4returntrue; 5 } else { 6returnfalse; 7 } 8 }
2、时间复杂度
使用如下代码来粗略比较不同实现间的时间复杂度。虽然不是很精确,但是思路确实正确的。我们将看看数组在有5、1k、10k个元素的情况下的不同表现。
5个
1 public static void main(String[] args) { 2 String[] arr = new String[]{"CD", "BC", "EF", "DE", "AB"}; 3 4// use list 5long startTime = System.nanoTime(); 6for (int i = 0; i < 100000; i++) { 7 useList(arr, "A"); 8 } 9long endTime = System.nanoTime(); 10long duration = endTime - startTime; 11 System.out.println("useList: " + duration / 1000000); 1213// use set14 startTime = System.nanoTime(); 15for (int i = 0; i < 100000; i++) { 16 useSet(arr, "A"); 17 } 18 endTime = System.nanoTime(); 19 duration = endTime - startTime; 20 System.out.println("useSet: " + duration / 1000000); 2122// use loop23 startTime = System.nanoTime(); 24for (int i = 0; i < 100000; i++) { 25 useLoop(arr, "A"); 26 } 27 endTime = System.nanoTime(); 28 duration = endTime - startTime; 29 System.out.println("useLoop: " + duration / 1000000); 3031// use Arrays . binarySearch ()32 startTime = System.nanoTime(); 33for (int i = 0; i < 100000; i++) { 34 useArraysBinarySearch(arr, "A"); 35 } 36 endTime = System.nanoTime(); 37 duration = endTime - startTime; 38 System.out.println("useArrayBinary: " + duration / 1000000); 39 }
结果
useList: 12 useSet: 65 useLoop: 2 useArrayBinary: 7
1k个元素
1 int length = 1000; 2 String[] arr = new String[length]; 34 Random s = new Random(); 5for (int i = 0; i < length; i++) { 6 arr[i] = String.valueOf(s.nextInt()); 7 }
结果
useList: 115 useSet: 2010 useLoop: 97 useArrayBinary: 9
10k个元素
1 int length = 10000; 2 String[] arr = new String[length]; 34 Random s = new Random(); 5for (int i = 0; i < length; i++) { 6 arr[i] = String.valueOf(s.nextInt()); 7 }
结果
useList: 1678 useSet: 25609 useLoop: 1802 useArrayBinary: 10
从上面的结果可以清晰看到,使用简单循环的相比使用其他集合操作更高效。很多很多开发人员使用第一种方法,但是它并不是最高效的。将数组转化成其他的任何集合类型都需要先将所有元素读取到集合类中,才能对这个集合类型做其他的事情。
当使用Arrays.binarySearch()
方法时,数组必须是排好序的。如果数组不是排好序的,则不能使用这个方法。
事实上,如果你真的需要高效地检查一个数组或者集合中是否包含一个值,一个排好序的数组或者树可以达到O(log(n))
的时间复杂度,HashSet
甚至能达到O(1)
的时间复杂度
转自http://www.diguage.com/archives/112.html
原文:http://www.cnblogs.com/dawnheaven/p/4469545.html
内容总结
以上是互联网集市为您收集整理的Java 高效检查一个数组中是否包含某个值全部内容,希望文章能够帮你解决Java 高效检查一个数组中是否包含某个值所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。