在Java中如何高效判断数组中是否包含某个元素

原文作者:Hollis_Chuang

原文地址:http://www.hollischuang.com/archives/1269

如何检查一个数组(无序)是否包含一个特定的值?这是一个在Java中经常用到的并且非常有用的操作。同时,这个问题在Stack Overflow中也是一个非常热门的问题。在投票比较高的几个答案中给出了几种不同的方法,但是他们的时间复杂度也是各不相同的。本文将分析几种常见用法及其时间成本。

检查数组是否包含某个值的方法

使用List

public static boolean useList(String[] arr, String targetValue) {
    return Arrays.asList(arr).contains(targetValue);}

使用Set

public static boolean useSet(String[] arr, String targetValue) {
    Set<String> set = new HashSet<String>(Arrays.asList(arr));
    return set.contains(targetValue);}

使用循环判断

public static boolean useLoop(String[] arr, String targetValue) {
    for(String s: arr){
        if(s.equals(targetValue))
            return true;
    }
    return false;

使用Arrays.binarySearch()

Arrays.binarySearch()方法只能用于有序数组!!!如果数组无序的话得到的结果就会很奇怪。

查找有序数组中是否包含某个值的用法如下:

public static boolean useArraysBinarySearch(String[] arr, String targetValue) { 
    int a =  Arrays.binarySearch(arr, targetValue);
    if(a > 0)
        return true;
    else
        return false;}

时间复杂度

下面的代码可以大概的得出各种方法的时间成本。基本思想就是从数组中查找某个值,数组的大小分别是5、1k、10k。这种方法得到的结果可能并不精确,但是是最简单清晰的方式。

public static void main(String[] args) {
    String[] arr = new String[] {  "CD",  "BC", "EF", "DE", "AB"};

    //use list
    long startTime = System.nanoTime();
    for (int i = 0; i < 100000; i++) {
        useList(arr, "A");
    }
    long endTime = System.nanoTime();
    long duration = endTime - startTime;
    System.out.println("useList:  " + duration / 1000000);

    //use set
    startTime = System.nanoTime();
    for (int i = 0; i < 100000; i++) {
        useSet(arr, "A");
    }
    endTime = System.nanoTime();
    duration = endTime - startTime;
    System.out.println("useSet:  " + duration / 1000000);

    //use loop
    startTime = System.nanoTime();
    for (int i = 0; i < 100000; i++) {
        useLoop(arr, "A");
    }
    endTime = System.nanoTime();
    duration = endTime - startTime;
    System.out.println("useLoop:  " + duration / 1000000);

    //use Arrays.binarySearch()
    startTime = System.nanoTime();
    for (int i = 0; i < 100000; i++) {
        useArraysBinarySearch(arr, "A");
    }
    endTime = System.nanoTime();
    duration = endTime - startTime;
    System.out.println("useArrayBinary:  " + duration / 1000000);}

运行结果:

useList:  13useSet:  72useLoop:  5useArraysBinarySearch:  9

使用一个长度为1k的数组

String[] arr = new String[1000];Random s = new Random();for(int i=0; i< 1000; i++){
    arr[i] = String.valueOf(s.nextInt());}

结果:

useList:  112useSet:  2055useLoop:  99useArrayBinary:  12

使用一个长度为10k的数组

String[] arr = new String[10000];Random s = new Random();for(int i=0; i< 10000; i++){
    arr[i] = String.valueOf(s.nextInt());}

结果:

useList:  1590useSet:  23819useLoop:  1526useArrayBinary:  12

总结

显然,使用一个简单的循环方法比使用任何集合都更加高效。许多开发人员为了方便,都使用第一种方法,但是他的效率也相对较低。因为将数组压入Collection类型中,首先要将数组元素遍历一遍,然后再使用集合类做其他操作。

如果使用Arrays.binarySearch()方法,数组必须是已排序的。由于上面的数组并没有进行排序,所以该方法不可使用。

实际上,如果你需要借助数组或者集合类高效地检查数组中是否包含特定值,一个已排序的列表或树可以做到时间复杂度为O(log(n)),hashset可以达到O(1)。

(英文原文结束,以下是译者注)


使用ArrayUtils

除了以上几种以外,Apache Commons类库中还提供了一个ArrayUtils类,可以使用其contains方法判断数组和值的关系。

import org.apache.commons.lang3.ArrayUtils;public static boolean useArrayUtils(String[] arr, String targetValue) {
    return ArrayUtils.contains(arr,targetValue);}

同样使用以上几种长度的数组进行测试,得出的结果是该方法的效率介于使用集合和使用循环判断之间(有的时候结果甚至比使用循环要理想)。

useList:  323useSet:  3028useLoop:  141useArrayBinary:  12useArrayUtils:  181-------useList:  3703useSet:  35183useLoop:  3218useArrayBinary:  14useArrayUtils:  3125

其实,如果查看ArrayUtils.contains的源码可以发现,他判断一个元素是否包含在数组中其实也是使用循环判断的方式。

部分代码如下:

    if(array == null) {
        return -1;
    } else {
        if(startIndex < 0) {
            startIndex = 0;
        }

        int i;
        if(objectToFind == null) {
            for(i = startIndex; i < array.length; ++i) {
                if(array[i] == null) {
                    return i;
                }
            }
        } else if(array.getClass().getComponentType().isInstance(objectToFind)) {
            for(i = startIndex; i < array.length; ++i) {
                if(objectToFind.equals(array[i])) {
                    return i;
                }
            }
        }

        return -1;
    }

所以,相比较之下,我更倾向于使用ArrayUtils工具类来进行一些合数祖相关的操作。毕竟他可以让我少写很多代码(因为自己写代码难免有Bug,毕竟apache提供的开源工具类库都是经过无数开发者考验过的),而且,效率上也并不低太多。

原文发布于微信公众号 - Java后端技术(JavaITWork)

原文发表时间:2016-11-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏不是你的bug

计算机是如何实现加法的

我们除去右下角看其他部分,和或运算结果是完全一致的。再单独看一下右下角,输入都为1时输出为0这不就是与非的操作结果吗。那我们将输入同时给到或门和与非门看下他们的...

39110
来自专栏潇涧技术专栏

Python Data Structures - C3 Data Structures

参考内容: 1.Problem Solving with Python Chapter 2 Algorithm Analysis Chapter 3 Ba...

7610
来自专栏小狼的世界

PHP中正则的使用

正则表达式,作为一种快速、便捷的处理字符串的工具,在各种编程语言中都有着广泛的用途,通过在PHP中的一些使用,下面记录一下关于PHP中正则使用的一些技巧。

13830
来自专栏深度学习之tensorflow实战篇

python 函数编程的位置参数、默认参数、关键字参数以及函数的递归

首先对于函数调用: !usr/bin/env python _*_ coding:utf-8 _*_ def AQA(INPUT): if INPUT...

28950
来自专栏一个会写诗的程序员的博客

《Kotlin 程序设计》第六章 Kotlin 函数式编程(FP)第六章 Kotlin 函数式编程(FP)1. 函数式编程概述2. Kotlin函数式编程参考资料

从本质上来说, 程序就是一系列有序执行的指令集合。 如何将指令集合组织成可靠可用可信赖的软件(美妙的逻辑之塔), 这是个问题。

13860
来自专栏屈定‘s Blog

算法回顾--如何写递归?

总之递归就是”装傻”的把原始的思路表现出来,不需要关心具体过程,只需要不停的缩小问题规模,然后答案自然就会被计算出来.

36020
来自专栏Java爬坑系列

【Java入门提高篇】Day3 抽象类与接口的比较

  抽象类跟接口都讲完了,现在来做一个比较。   其实说实话,没有多大的可比较性,它们是完全不同的两个东西,它们的抽象不在同一个层级上。但是为了让大家更好的理解...

19270
来自专栏MyBlog

Effective.Java 读书笔记(11)关于clone方法

说到clone方法,我们来提一提Cloneable这个接口,这个接口是用来作为一种标记某对象允许被clone的一种混合接口,可是不幸运的是,这个接口并没能起到该...

11620
来自专栏java一日一条

如何读懂并写出装逼的函数式代码

今天在微博上看到了 有人分享了下面的这段函数式代码,我把代码贴到下面,不过我对原来的代码略有改动,对于函数式的版本,咋一看,的确令人非常费解,仔细看一下,你可能...

7320
来自专栏进击的君君的前端之路

Math对象、数组、日期函数

16750

扫码关注云+社区

领取腾讯云代金券