服务器之家：专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - Java教程 - Java中高效判断数组中是否包含某个元素的几种方法

Java中高效判断数组中是否包含某个元素的几种方法

2022-01-07 13:10hollis Java教程

这是一个在Java中经常用到的并且非常有用的操作，这个问题在Stack Overflow中也是一个非常热门的问题，本文将分析几种常见用法及其时间成本

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

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

使用List

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

使用Set

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

使用循环判断

?
1
2
3
4
5
6
7
public static boolean useLoop(String[] arr, String targetValue) {
    for(String s: arr){
        if(s.equals(targetValue))
            return true;
    }
    return false;
}

使用Arrays.binarySearch()

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

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

?
1
2
3
4
5
6
7
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。这种方法得到的结果可能并不精确，但是是最简单清晰的方式。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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: 13
useSet: 72
useLoop: 5
useArraysBinarySearch: 9

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

?
1
2
3
4
5
6
String[] arr = new String[1000];
 
Random s = new Random();
for(int i=0; i< 1000; i++){
    arr[i] = String.valueOf(s.nextInt());
}

结果：

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

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

?
1
2
3
4
5
6
String[] arr = new String[10000];
 
Random s = new Random();
for(int i=0; i< 10000; i++){
    arr[i] = String.valueOf(s.nextInt());
}

结果：

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

总结

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

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

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

（英文原文结束，以下是译者注）

补充

使用ArrayUtils

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

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

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

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

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

部分代码如下：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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提供的开源工具类库都是经过无数开发者考验过的），而且，效率上也并不低太多。

完整测试代码

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
package zaLearnpackage;
import org.apache.commons.lang3.ArrayUtils;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
//检查数组是否包含某个值的方法
public class TestArray {
    //使用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;
    }
//查找有序数组中是否包含某个值的用法
public static boolean useArraysBinarySearch(String[] arr,String targetValue){
    int a=Arrays.binarySearch(arr, targetValue);
    if(a>0)
        return true;
    else
        return false;
}
//使用ArrayUtils
public static boolean useArrayUtils(String[] arr,String targetValue){
    return ArrayUtils.contains(arr,targetValue);
}
public static void main(String[] args) {
    String[] arr=new String[]{"CD","BC","EF","DE","AB","JK"};
    //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
        long startTime2=System.nanoTime();
        for(int i=0;i<100000;i++){
            useSet(arr, "A");
        }
        long endTime2=System.nanoTime();
        long duration2=endTime2-startTime2;
        System.out.println("useSet:"+duration/1000000);
        //use loop
        long startTime3=System.nanoTime();
        for(int i=0;i<100000;i++){
            useLoop(arr, "A");
        }
        long endTime3=System.nanoTime();
        long duration3=endTime3-startTime3;
        System.out.println("useLoop:"+duration/1000000);
        //use Arrays.binarySearch()
        long startTime4=System.nanoTime();
        for(int i=0;i<100000;i++){
            useArraysBinarySearch(arr, "A");
        }
        long endTime4=System.nanoTime();
        long duration4=endTime4-startTime4;
        System.out.println("useArraysBinarySearch:"+duration/1000000);
}
}
/*
 * 显然，使用一个简单的循环方法比使用任何集合都更加高效。许多开发人员为了方便，都使用第一种方法，但是他的效率也相对较低。因为将数组压入Collection类型中，首先要将数组元素遍历一遍，然后再使用集合类做其他操作。
 */

长字符串数据

遇到一些有规律的长字符串数据的解决办法（找到是否存在要查找的元素，非遍历）

?
1
2
3
4
5
6
7
8
String inputStrs = "北京,天津,上海,四川,湖南,广州,深圳,海南";
String[] strList = inputStrs.split(",");
 
String target = "上海";//1
String result = Arrays.asList(strList).contains(target) ? "查到咯！" : "没这个城市啊...";
//2Set<String> set = new HashSet<>(Arrays.asList(strList));
System.out.println(set.contains(target)); // true
System.out.println(result); // result="查到咯！"-----------

到此这篇关于Java中高效判断数组中是否包含某个元素的几种方法的文章就介绍到这了,更多相关Java包含某个元素判断内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！

原文链接：http://www.hollischuang.com/archives/1269

  • Java
  • 数组
  • 元素
  • 包含

    • 延伸 · 阅读

    精彩推荐
    最近更新
    编辑推荐
    阅读排行
    热门标签
    501 　 406 　 415 　 1433 　 2000 　 401 　 330 　 GOF23 　 堆栈类 　 微信公众号 　 注册服务 　 嵌套循环 　 critical 　 consul 　 spring 　 集合 　 volatile 　 Hibernate 　 Java 　 new 　 double 　 泛型 　 Java编程 　 遍历 　 设计模式 　 supplyAsync 　 制表符 　 回车 　 写入文件 　 JAVA8 　
    © 2019-2024 服务器之家(www.zzvips.com) 版权所有关于我们联系我们版权申明网站地图