快速的判断两个字符串型数组是否有交集

原创
2015/07/02 19:31
阅读数 2K

■[面试题]如何快速的判断两个数组是否有交集

public boolean hasIntersection(String[] array1, String[] array2) {

     ...

}

array1中,只要有一个在array2中,存在,就返回true,否则返回false

求最快的方法


原帖:http://www.oschina.net/question/1756518_241715


■代码

--------------------------------------------------------------------------------

package javay.test;


import java.util.Arrays;

import java.util.HashMap;

import java.util.PriorityQueue;

import java.util.TreeMap;


public class TestIntersection {

    public boolean hasIntersectionByHashMap(String[] array1, String[] array2) {

        HashMap<String, String> map = new HashMap<String, String>();

        for(String str : array2) {

            map.put(str, str);

        }

        for (String str : array1) {

            if (map.get(str) != null) {

                return true;

            }

        }

        return false;

    }

    public boolean hasIntersectionByTreeMap(String[] array1, String[] array2) {

        TreeMap<String, String> map = new TreeMap<String, String>();

        for(String str : array2) {

            map.put(str, str);

        }

        for (String str : array1) {

            if (map.get(str) != null) {

                return true;

            }

        }

        return false;

    }

    public boolean hasIntersectionByIndexOf(String[] array1, String[] array2) {

        String map = Arrays.toString(array2);

        for (String str : array1) {

            if (map.indexOf(str) > -1) {

                return true;

            }

        }

        return false;

    }

    public boolean hasIntersectionBySortBS(String[] array1, String[] array2) {

        Arrays.sort(array2);

        for (String str : array1) {

            if (Arrays.binarySearch(array2, str) > -1) {

                return true;

            }

        }

        return false;

    }

    public boolean hasIntersectionByPQueue(String[] array1, String[] array2) {

        PriorityQueue<String> queue = new PriorityQueue<String>(array2.length);

        for(String str : array2) {

            queue.offer(str);

        }

        for (String str : array1) {

            if (queue.contains(str)) {

                return true;

            }

        }

        return false;

    }

    public static void main(String[] args) {

        int nMax = 4000000;

        String[] b = new String[nMax];

        for (int i = 0; i < nMax ; i ++) {

            b[i] = String.valueOf(i);

        }


        String[] t = new String[1];

        t[0] = String.valueOf(nMax - 1) + "x";

        TestIntersection proc = new TestIntersection();


        long a = System.currentTimeMillis();

        System.out.println("HashMap:" + proc.hasIntersectionByHashMap(t, b) + "," + (System.currentTimeMillis() - a));


        a = System.currentTimeMillis();

        System.out.println("TreeMap:" + proc.hasIntersectionByTreeMap(t, b) + "," + (System.currentTimeMillis() - a));


        a = System.currentTimeMillis();

        System.out.println("IndexOf:" + proc.hasIntersectionByIndexOf(t, b) + "," + (System.currentTimeMillis() - a));


        a = System.currentTimeMillis();

        System.out.println("PQueue :" + proc.hasIntersectionByPQueue(t, b) + "," + (System.currentTimeMillis() - a));


        a = System.currentTimeMillis();

        System.out.println("SortBS :" + proc.hasIntersectionBySortBS(t, b) + "," + (System.currentTimeMillis() - a));


        for (int i = (nMax - 1); i >= 0 ; i --) {

            b[nMax - i - 1] = String.valueOf(i);

        }

        System.out.println();


        a = System.currentTimeMillis();

        System.out.println("HashMap:" + proc.hasIntersectionByHashMap(t, b) + "," + (System.currentTimeMillis() - a));


        a = System.currentTimeMillis();

        System.out.println("TreeMap:" + proc.hasIntersectionByTreeMap(t, b) + "," + (System.currentTimeMillis() - a));


        a = System.currentTimeMillis();

        System.out.println("IndexOf:" + proc.hasIntersectionByIndexOf(t, b) + "," + (System.currentTimeMillis() - a));


        a = System.currentTimeMillis();

        System.out.println("PQueue :" + proc.hasIntersectionByPQueue(t, b) + "," + (System.currentTimeMillis() - a));


        a = System.currentTimeMillis();

        System.out.println("SortBS :" + proc.hasIntersectionBySortBS(t, b) + "," + (System.currentTimeMillis() - a));

    }

}

--------------------------------------------------------------------------------

■测试结果

HashMap:false,4744

TreeMap:false,7159

IndexOf:false,875

PQueue :false,499

SortBS :false,469★


HashMap:false,6326

TreeMap:false,4666

IndexOf:false,495

PQueue :false,453

SortBS :false,421★


但也有例外的结果。

HashMap:false,4635

TreeMap:false,7257

IndexOf:false,859

PQueue :false,468★

SortBS :false,484


HashMap:false,6344

TreeMap:false,4712

IndexOf:false,588

PQueue :false,437

SortBS :false,417★


展开阅读全文
打赏
0
11 收藏
分享
加载中
如比如比博主
Arrays是对array的操作,然Collections却不是对Collection的操作。69
2015/07/03 05:13
回复
举报
如比如比博主
这里不能帖码?10
2015/07/03 05:10
回复
举报
如比如比博主

引用来自“GenesisKing”的评论

直接都放set里 最后比较set大小与两个数组长度和 等于就没有交集
public boolean hasIntersectionByHashSet2(String[] array1, String[] array2) { HashSet set = new HashSet(); HashSet set1 = new HashSet(); for(String str : array2) { // for each set.add(str); } int sa2 = set.size(); for (String str : array1) { // for each set1.add(str); } int sa1 = set1.size(); set.addAll(set1); // for each int sall = set.size(); // System.out.println("@hasIntersectionByHashSet2[" + sa1 + "," + sa2 +"," + sall + "]"); return sall == (sa1 + sa2) ? false : true; }
2015/07/03 05:08
回复
举报
如比如比博主

引用来自“zouqilin”的评论

写了这么长的一段代码能是最快的么 ruby insect=a&b
只有更好,没有最好。
2015/07/03 04:07
回复
举报
写了这么长的一段代码能是最快的么 ruby insect=a&b
2015/07/03 00:19
回复
举报
直接都放set里 最后比较set大小与两个数组长度和 等于就没有交集
2015/07/02 21:23
回复
举报
如比如比博主
目前感觉排序加二分有优势。没有完全测试。
2015/07/02 21:20
回复
举报
哪个最快
2015/07/02 21:14
回复
举报
更多评论
打赏
8 评论
11 收藏
0
分享
返回顶部
顶部