小伙伴们注意了!
小编在这里给大家送上关注福利:
转发本文, 关注 + 私信小编 "资料" 即可领取小编精心准备的资料一份
如何检查数组 (未排序) 是否包含某个值?
这是 Java 中非常有用且经常使用的操作.
这也是一个关于堆栈溢出的投票最多的问题.
正如投票结果显示的那样, 这可以通过几种不同的方法来实现, 但是时间复杂度可能会非常不同.
下面我将展示每种方法的时间成本.
1. 检查数组是否包含值的四种不同方法
1)使用列表:
2)使用设置:
3)使用一个简单的循环:
4)使用 Arrays.binarySearch ():
binarySearch()只能用于排序数组.
如果数组已排序, 可以使用以下代码搜索目标元素:
2. 时间复杂度
近似的时间成本可以用下面的代码来测量.
基本思想是搜索大小为 5,1k, 10k 的数组.
这种方法可能不精确, 但其思想是清晰和简单的.
结果 :
使用更大的数组(1k):
结果:
使用更大的数组(10k):
结果:
显然, 使用简单的 loop 方法比使用任何集合都更有效.
很多开发人员都使用第一种方法, 但是这种方法效率很低.
将数组推入另一个集合需要遍历所有元素, 以便在处理集合类型之前读取它们.
如果使用 Arrays.binarySearch()方法, 则必须对数组进行排序.
在这种情况下, 数组没有排序, 因此不应该使用它.
实际上, 如果需要检查某个值是否有效地包含在某个数组 / 集合中, 排序列表或树可以在 O(log(n))中执行, 或者 hashset 可以在 O(1)中执行.
最后, 想学习 Java 的小伙伴们!
关注 "速学 java" 公众号就可以拿到一份我为大家准备的 Java 学习资料!
对 Java 感兴趣的小伙伴也可以加 小编 V: suxuejava
来源: http://www.jianshu.com/p/af2f290280f5