如何高效地判断数组中是否包含某特定值

如何检查一个未排序的数组中是否包含某个特定值,这是一个在Java中非常实用并且频繁使用的操作。另外,这也是Stack Overflow上面非常受关注的问题。在得票数最多的答案中,可以看到,检查数组中是否包含特定值可以用多种不同的方式实现,但是时间复杂度差别很大。下面,我将为大家展示各种方法及其需要花费的时间。

1.检查数组中是否包含特定值的四种不同方法

1)使用List:

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

2)使用Set:

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

3)使用一个简单循环:

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

4)使用Arrays.binarySearch():

注:下面的代码是错误的,这样写出来仅仅为了理解方便。binarySearch()只能用于已排好序的数组中。所以,你会发现下面结果很奇怪。

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

2.时间复杂度

通过下面的这段代码可以近似比较几个方法的时间复杂度。虽然分别搜索一个大小为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:  13
    useSet:  72
    useLoop:  5
    useArraysBinarySearch:  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:  112
    useSet:  2055
    useLoop:  99
    useArrayBinary:  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:  1590
    useSet:  23819
    useLoop:  1526
    useArrayBinary:  12

很明显,使用简单循环的方法比使用其他任何集合效率更高。许多开发者会使用第一种方法,但是它并不是高效的。将数组压入Collection类型中,需要首先将数组元素遍历一遍,然后再使用集合类做其他操作。

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

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

原文链接: programcreek 翻译: ImportNew.com - 0x0bject
译文链接: http://www.importnew.com/10937.html
[ 转载请保留原文出处、译者和译文链接。]

关于作者: 0x0bject

(新浪微博:@0x0bject

查看0x0bject的更多文章 >>



相关文章

发表评论

Comment form

(*) 表示必填项

14 条评论

  1. kent kwan 说道:

    这种文章……..自后用binarySearch也不对数组进行排序性能的测试

    Thumb up 0 Thumb down 0

  2. hackem 说道:

    “hashset可以达到O(1)” hashset怎么会是O(1)呢,明显不是常量啊

    Thumb up 0 Thumb down 0

  3. Michael 说道:

    这里的 “hashset可以达到O(1)” 没有在时间上体现出来啊?
    而且你每次调用useSet(arr,”A”)的时候都要执行一次arr转化为hashSet。这个转化的时间怎么能算在内呢?

    Thumb up 2 Thumb down 1

  4. Michael 说道:

    如果不把数组转化为hashset或list的时间考虑在内的话。他们的时间如下:
    array长度为5
    useList: 7
    useSet: 11
    useLoop: 5

    array长度为1000
    useList: 145
    useSet: 9
    useLoop: 125

    array长度为10000
    useList: 1970
    useSet: 7
    useLoop: 1669

    就简单改了下你的代码。没有用binarySearch。

    Thumb up 2 Thumb down 0

  5. Kenny Soung 说道:

    用HashSet快是因为创建HashSet时已经将位置放好了(hash),基本就只是去相应的位置拿,它应该是比binarySearch还要快的。但是效率损耗在了创建Set时。

    Thumb up 0 Thumb down 0

  6. MITEL 说道:

    简直是:无中生有的问题。

    Thumb up 3 Thumb down 1

  7. JavaNew 说道:

    分析比较浅显

    Thumb up 1 Thumb down 0

  8. 李火亮 说道:

    我觉得作者这样测试没错,标题已经说了如何高效的判断数组中是否包含某元素,给出一个数组的话要判断是否包换某个元素,需要将数组转集合的消耗也算进去,不然就不符合这篇文章的本意了。

    Thumb up 1 Thumb down 0

  9. 夕辞 说道:

    比较适合入门的,不过就像评论的,该文章的知识点确实没有太大作用

    Thumb up 0 Thumb down 0

  10. ice 说道:

    然而作者的循环没有按照数组的特点(连续)遍历,下面的代码在时间效率上更好,尽管多了代码量:
    public static boolean useLoop2(String[] arr, String targetValue) {
    for(int i=0; i<arr.length; i++){
    if(targetValue.equals(arr[i]))
    return true;
    }
    return false;
    }

    Thumb up 0 Thumb down 1

  11. 小新星 说道:

    赞一个,

    Thumb up 0 Thumb down 0

跳到底部
返回顶部