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

标签: 基础技术 数组 | 发表时间:2014-04-21 00:00 | 作者:0x0bject
出处:http://www.importnew.com

如何检查一个未排序的数组中是否包含某个特定值,这是一个在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)。

可能感兴趣的文章

相关 [数组 包含] 推荐:

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

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

测试Jsp 静态包含和动态包含

- - CSDN博客Web前端推荐文章
静态包含是在请求包含页面时去编译包含页面,编译时遇到静态页面包含伪码将被包含页面的内容复制到被包含页面中进行编译. 动态包含是指在请求包含页面的时候遇到动态包含指令将请求转到被包含页面,这时去编译被包含页面. 但两者生成的class文件缺不同:. 通过以上说明可知,动态包含在请求到来时编译包含页面和被包含页面,如果都是jsp页面,那么将生成两个个页面对应的class文件和java文件.

Safari 5.0.1到来 包含扩展中心

- tom - cnBeta.COM
带有扩展的Safari浏览器终于来了,这意味着Firefox和Chrome终于迎来了新对手. 这就是苹果最新发布的带有5.0.1版本,新版不但带来了HTML5和CSS3以及JavaScript新标准支持,最重要的是Safari Extensions Gallery特性,首批为苹果制作扩展的厂商有MLB.com, The New York Times和Twitter、eBay等大户人家,扩展中心也可以通过访问extensions.apple.com抵达.

包含西方文化的英语短句

- 晓江 - 每日英语
  有些句子我们在电影里面经常听到,但对于它们的确切意思可能并不是很了解,下面我们一起来看几个这样的句子吧.   如果外国夫妇请你到家里吃饭,看着一桌丰盛的酒席,你问他们可以开始吃了吗,他们通常会说“Sure. 当两个小孩子在相互追逐玩乐,互相打斗的时候,一个通常会主动碰了一下另一个,然后说“哈哈,打到你了.

BUILD: Windows 8 包含手机呼叫和短信功能

- Lionheart - LiveSino - LiveSide 中文版
Long Zheng 在 BUILD Session 中注意到了一张幻灯片显示的“未接来电”瓷片,这暗示了 Windows 8 将内置手机电话呼叫功能,同时也使得 Windows Phone OS 的未来更加难以琢磨. 其次,我们也可以在 Windows Live 应用演示中看到,人脉(即 People)应用中明确显示了可以发送短信和拨打手机,而且支持 Threads 功能:.

[图]Windows8依然包含“经典模式”的蓝屏

- Darth Noctis - cnBeta.COM
Win8再一次蓝屏了,本次蓝屏出现在启动过程中,可爱的笑脸不知道哪里去了,那个标志性的Windows又回来了…….

Windows 8 首批下载将包含中文等5种语言

- Tolay - cnBeta.COM
微软的Windows 8版本保密机制无疑是做的最好的,有史以来也是泄漏版本最少的. 现在,随着9月13日Build Windows大会的临近,一切都意味着微软Windows 8的公开下载即将开始. 除了针对开发者(编程人员)的Windows Developer Preview(开发者预览版本),Windows 8 Beta公测版本也将在随后的几天内放开下载.

《质量效应3》将包含多人合作模式

- lin - Solidot
BioWare宣布,将于明年三月发布的《质量效应3》将包含一个多人合作游戏模式. 根据官方论坛的介绍,在《质量效应3》中,BioWare引入了Galaxy at War系统去管理和体验多人模式,多人模式由四人参与. 玩家无法扮演单人游戏中的指挥官Shepard,Garrus、Ashley和Liara等,但可以扮演Turians、Krogans和Asari,玩家可以定制角色、种族和特殊能力,可以通过多人游戏提升等级和武器.

CyanogenMod 7.1正式版发布 包含最新Android系统2.3.7

- kxxoling - cnBeta.COM
知名的第三方Android定制系统开发团队CM今日发布了最新的作品,CyanogenMod 7.1版. 此次更新的内容非常庞大,主要工作围绕Bug修复和外观改变上展开. 但这一版本最重要也是最引人注意的是,CM7.1现在提供的系统为最新的Android 2.3.7.

微软禁止Windows 8应用名称包含“Metro”

- - 快乐无极的博客
北京时间8月16日早间消息,微软已对Windows Store应用商店的应用命名规则进行更新,要求所有应用的名称中不得含有“Metro”字样,而以“Metro”命名的应用将不能通过审核,从而无法进入Windows Store.   为了避免与德国合作伙伴Metro AG之间的商标权纠纷,微软已决定放弃使用Metro品牌.