如何高效的判断一个数组里是否含特定元素判断一个数组里是否含有特定元素的四种方法时间复杂度测试小结

desperate633

发布于 2018-08-22 15:48:28

1.2K0

发布于 2018-08-22 15:48:28

文章被收录于专栏：desperate633

如何高效的判断一个数组里是否含特定元素？这是我们在实际开发中经常遇到的一个问题，也是在Stack Overflow上的热门问题，解决这个问题有很多不同的方法，但是不同的方法的时间复杂度却差别很大，所以本文会列举常用的几种方法，并且对比每个方法的耗时，找出相对最高效的方法。

判断一个数组里是否含有特定元素的四种方法

使用list

//Using List
    public static boolean useList(String[] arr, String targetVal) {
        return Arrays.asList(arr).contains(targetVal);
    }

使用set

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

使用简单的for循环

//Using a simple loop
    public static boolean loop(String[] arr,String targetVal) {
        for(String s:arr)
            if(s.equals(targetVal))
                return true;
        return false;
    }

二分查找下面的代码是不可用的，因为我们知道二分查找只是用于有序的数组。

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

时间复杂度测试

我们可以用大量的数据来重复测试，以放大各个方法之间的执行时间的差别。

public static void main(String[] args) {
        
        String[] arr = new String[] { "CD", "BC", "EF", "DE", "AB"};
        
        //using list
        long startTime = System.nanoTime();
        
        for(int i=0;i<1000000;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 < 1000000; 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 < 1000000; i++) {
         loop(arr, "A");
        }
        endTime = System.nanoTime();
        duration = endTime - startTime;
        System.out.println("useLoop: " + duration / 1000000);

    }

Paste_Image.png

看出测试结果，竟然是直接使用简单的循环效率是最高的。显然，如果数组已经排好序的情况下，我们应该使用二分查找的方法。

接下来，我们再使用一个大的Array来测试一下

public static void main(String[] args) {
        
        String[] arr = new String[1000];
        Random s = new Random();
        for(int i=0; i< 10000; i++){
            arr[i] = String.valueOf(s.nextInt());
        }
        //String[] arr = new String[] { "CD", "BC", "EF", "DE", "AB"};
        
        //using list
        long startTime = System.nanoTime();
        
        for(int i=0;i<1000000;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 < 1000000; 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 < 1000000; i++) {
         loop(arr, "A");
        }
        endTime = System.nanoTime();
        duration = endTime - startTime;
        System.out.println("useLoop: " + duration / 1000000);

    }

Paste_Image.png

我们发现测试结果还是直接使用循环来的更快。

小结

我们发现当数组是无序的时候，我们如果要判断一个数组中是否含有一个元素，应该使用直接的循环查找，这样效率是最高的，如果数组是有序的情况下，我们应该使用二分查找，此外，如果是在hashset或hashmap中查找一个元素直接调用collection的库就可以了。

转自http://www.programcreek.com/simple-java/

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017.03.25 ，如有侵权请联系 cloudcommunity@tencent.com 删除

其他

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

其他

登录后参与评论

0 条评论

热度