在Java中怎样高效的推断数组中是否包括某个元素

来自 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:  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)。

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

使用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:  323
useSet:  3028
useLoop:  141
useArrayBinary:  12

useArrayUtils: 181

useList:  3703
useSet:  35183
useLoop:  3218
useArrayBinary:  14
useArrayUtils:  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提供的开源工具类库都是经过无数开发人员考验过的),并且,效率上也并不低太多。

时间: 07-23

在Java中怎样高效的推断数组中是否包括某个元素的相关文章

【c语言】二维数组中的查找,杨氏矩阵在一个二维数组中,每行都依照从左到右的递增的顺序排序,输入这种一个数组和一个数,推断数组中是否包括这个数

// 二维数组中的查找,杨氏矩阵在一个二维数组中.每行都依照从左到右的递增的顺序排序. // 每列都依照从上到下递增的顺序排序.请完毕一个函数,输入这种一个数组和一个数.推断数组中是否包括这个数 #include <stdio.h> #define col 4 #define rol 4 int yang(int(*p)[col], int num) { int i = 0; int j = col - 1; while (j+1) { int *q = &(p[i][j]); if

将一个任意整数插入到已排列的整型数组中,插入后,数组中的数仍保持有序

实现代码: package homework; import java.util.Scanner; public class HomeWork { public static void main(String[] args) { //將输入的数字插入到一个有序的数组中的合适位置 Scanner input = new Scanner(System.in); System.out.println("请输入一个数字:"); int num = input.nextInt(); //有序的整

java中将int类型数据存到数组中

//定义一个数据 int number = 123456; //定义一个数组 int[] arr = new int[8]; //通过观察这个代码,我们发现应该是可以通过循环改进的 int index = 0; while(number > 0) { //number=123456,number=12345,number=1234,number=123,number=12,number=1,number=0 arr[index] = number%10; //arr[0]=6,arr[1]=5,

冒泡排序--通过冒泡算法让数组中最大的值成为数组中最后一个值

var nums = [];//定义一个空数组 for(var i=0;i<5;i++){//要用户输入五个数字,就循环5次 nums[i] = parseInt(prompt('请输入数字'));//使用for循环,prompt提示的方法提示用户输入数字 } console.log('用户输入的是:'); console.log(nums);//打印出用户输入的全部数字 for(var i=0;i<nums.length-1;i++){ for(var j=0;j<nums.lengt

剑指Offer面试题36(Java版):数组中的逆序对

题目:在数组中的两个数字如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对.输入一个数组,求出这个数组中的逆序对的总数 例如在数组{7,5,6,4}中,一共存在5对逆序对,分别是{7,6},{7,5},{7,4},{6,4},{5,4}. 看到这个题目,我们的第一反应就是顺序扫描整个数组.每扫描到一个数组的时候,逐个比较该数字和它后面的数字的大小.如果后面的数字比它小,则这两个数字就组成一个逆序对.假设数组中含有n个数字.由于每个数字都要和O(n)个数字做比较,因此这个算法的时间复杂度为

剑指Offer面试题29(java版):数组中出现次数超过一半的数字

题目:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字.例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}.由于数字2在数组中出现5次,超过数组长度的一半,因此输出2. 解法一:基于Partition函数的O(n)算法: 我们的算法是受快速排序的算法的启发.在随机快速排序的算法中,我们先在数组中随机的选择一个数字,然后调数组中数字的顺序,使得比选中的数字小数字排在它的左边,比选中的数字大的数字都排在它的右边.比如这个选中的数字的下标刚好是n/2,那么这个数字就是数组中的

java程序练习:数组中随机10个数中的最大值

//定义输入:其实是一个可以保存10个整数的数组 //使用循环遍历,生成10个随机数,放入每个元素中//打桩,数组中的内容 //定义输出变量 //将数组中第一个元素取出,保存在max中,当靶子 //遍历数组,从第二个元素[1]开始,都和max比较 //如果任何元素超过max,就取而代之//输出max

【白话经典算法系列之十七】 数组中只出现一次的数 其他三次

本文地址:http://blog.csdn.net/morewindows/article/details/12684497转载请标明出处,谢谢. 欢迎关注微博:http://weibo.com/MoreWindows 首先看看题目要求: 数组A中,除了某一个数字x之外,其他数字都出现了三次,而x出现了一次.请给出最快的方法找到x. 这个题目非常有意思,在本人博客中有<位操作基础篇之位操作全面总结>这篇文章介绍了使用位操作的异或来解决——数组中其他数字出现二次,而x出现一次,找出x.有<

再回首,Java温故知新(十):数组

数组是程序中用来存储同一类型值的集合,基本所有编程语言中都有这种类型存在.声明数组时需要指出数组类型和数组变量名,初始化后数组的长度不可变,使用过程中通过下标来访问数组中的元素,示例代码如下: int[] a;//声明整数型数组 a = new int[10];//初始化一个长度为10的整型数组 System.out.println(a[0]); 注:声明数组时有两种写法,一种是int[] a,另一种死int a[],推荐使用第一种,因为类型和变量名分开,容易理解. 关于数组的排序经常会出现在笔