首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

灵魂拷问:如何检查Java数组中是否包含某个值?

如何检查数组(未排序)中是否包含某个值 ?这是一个非常有用并且经常使用的操作。我想大家的脑海中应该已经浮现出来了几种解决方案,这些方案的时间复杂度可能大不相同。

我先来提供四种不同的方法,大家看看是否高效。

1)使用 List

Arrays 类中有一个内部类 ArrayList(可以通过 Arrays.asList(arr) 创建该实例),其 contains() 方法的源码如下所示。

从上面的源码可以看得出,contains() 方法调用了 indexOf() 方法,如果返回 -1 则表示 ArrayList 中不包含指定的元素,否则就包含。其中 indexOf() 方法用来获取元素在 ArrayList 中的下标,如果元素为 null,则使用“==”操作符进行判断,否则使用 equals() 方法进行判断。

PS:关于“==”操作符和 equals() 方法,可以参照我另外一篇文章《如何比较 Java 的字符串?》

2)使用 Set

HashSet 其实是通过 HashMap 实现的,当使用 new HashSet(Arrays.asList(arr)) 创建并初始化了 HashSet 对象后,其实是在 HashMap 的键中放入了数组的值,只不过 HashMap 的值为默认的一个摆设对象。大家感兴趣的话,可以查看一下 HashSet 的源码。

我们来着重看一下 HashSet 的 contains() 方法的源码。

从上面的源码可以看得出,contains() 方法调用了 HashMap 的 containsKey() 方法,如果指定的元素在 HashMap 的键中,则返回 true;否则返回 false。

3)使用一个简单的循环

for-each 循环中使用了 equals() 方法进行判断——这段代码让我想起了几个词,分别是简约、高效、清晰。

4)使用 Arrays.binarySearch()

不过,binarySearch() 只适合查找已经排序过的数组。

由于我们不确定数组是否已经排序过,所以我们先来比较一下前三种方法的时间复杂度。由于调用 1 次的时间太短,没有统计意义,我们就模拟调用 100000 次,具体的测试代码如下所示。

PS:nanoTime() 获取的是纳秒级,这样计算的时间就更精确,最后除以 1000000 就是毫秒。换算单位是这样的:1秒=1000毫秒,1毫秒=1000微秒,1微秒=1000纳秒。

统计结果如下所示:

假如把数组的长度增加到 1000,我们再来看一下统计结果。

这时数组中是没有我们要找的元素的。为了做比较,我们顺便把二分查找也添加到统计项目中。

统计结果如下所示:

我们再把数组的长度调整到 10000。

统计结果如下所示:

从上述的统计结果中可以很明显地得出这样一个结论:使用简单的 for 循环,效率要比使用 List 和 Set 高。这是因为把元素从数组中读出来再添加到集合中,就要花费一定的时间,而简单的 for 循环则省去了这部分时间。

在得出这个结论之前,说实话,我最喜欢的方式其实是第一种“使用 List”,因为只需要一行代码 Arrays.asList(arr).contains(targetValue) 就可以搞定。

虽然二分查找(Arrays.binarySearch())花费的时间明显要少得多,但这个结论是不可信的。因为二分查找明确要求数组是排序过的,否则查找出的结果是没有意义的。

实际上,如果要在一个数组或者集合中有效地确定某个值是否存在,一个排序过的 List 的算法复杂度为 O(logn),而 HashSet 则为 O(1)。

我们再来发散一下思维:怎么理解 O(logn) 和 O(1) 呢?

O(logn) 的算法复杂度,比较典型的例子是二分查找。举个例子,假设现在一堆试卷,已经按照分数从高到底排列好了。现在要查找有没有 79 分的试卷,怎么办呢?可以先从中间找起,因为按照 100 分的卷子来看,79 分大差不差应该就在中间的位置(平均分如果低于 79 说明好学生就比较少了),如果中间这份卷子的分数是 83,那说明 79 分的卷子就在下面的一半,这时候可以把上面那半放在一边了。然后按照相同的方式,每次就从中间开始找,直到找到 79 分的卷子(当然也可能没有 79 分)。

假如有 56 份卷子,找一次,还剩 28 份,再找一次,还剩 14 份,再找一次,还剩 7 份,再找一次,还剩 2 或者 3 份。如果是 2 份,再找一次,就只剩下 1 份了;如果是 3 份,就还需要再找 2 次。

我们知道,log2(32) = 5,log2(64) = 6,而 56 就介于 32 和 64 之间。也就是说,二分查找大约需要 log2(n) 次才能“找到”或者“没找到”。而在算法复杂度里,经常忽略常数,所以不管是以 2 为底数,还是 3 为底数,统一写成 log(n) 的形式。

再来说说 O(1),比较典型的例子就是哈希表(HashSet 是由 HashMap 实现的)。哈希表是通过哈希函数来映射的,所以拿到一个关键字,通过哈希函数转换一下,就可以直接从表中取出对应的值——一次直达。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20191218A06RBA00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券