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

西夏一品堂 发布于 2015/07/01 23:22
阅读 5K+
收藏 3
public boolean hasIntersection(String[] array1, String[] array2)
{
     ...
}


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

求最快的方法



加载中
0
leo108
leo108

hashmap

西夏一品堂
西夏一品堂
这样还是要循环两次
leo108
leo108
回复 @西夏一品堂 : 遍历arr1填充hashmap,遍历arr2看是否存在对应的key,时间复杂度O(n)
西夏一品堂
西夏一品堂
能具体点吗?
0
hyjiacan
hyjiacan
arr2 join 使用特定字符成字符串,然后遍历arr1,在字符串中找arr1的元素。
maosi
maosi
arr1[0] = "a,b"; arr2[0] = "a"; arr2[1] = "b"; 这种情况下不行
0
God20134
God20134
放入 Set中,判断Set和arr1+arr2的长度是否相等
0
梅开源
梅开源

应该反问

是要人快还是要算法快

如果数组非常大怎么办

0
qjf_Troy
qjf_Troy

引用来自“God20134”的评论

放入 Set中,判断Set和arr1+arr2的长度是否相等
开始也觉得用这个方法,但是好像如果使用map,在第二次便利的时候如果发现又key和arr2相等的则跳出循环,这样好像会比用set遍历两边效率高点
qjf_Troy
qjf_Troy
回复 @de虫子 : 如果数组元素很多,我之遍历一次数组,放入map中,第二次之比较key相等就跳出,不用遍历后续的,怎么都比全部遍历效果要好。你用set判断最后的size怎么也要遍历两遍吧,还有大家都是讨论,不要用什么反问,真以为别人不会用反问吗,还是不要太高傲了
d
de虫子
每次都要判断key和arr2是否有重复 , 你确定这不会浪费时间? 这样还不如 全部遍历,最后判断长度. 如果优化一下, 每次记录遍历的次数, 每隔一定次数, 比较一次map的大小 , 如果不等, 退出循坏, 返回false.
猜猜我是吧
猜猜我是吧
少年,你知道Set内部是怎么实现的么,貌似是红黑树还是什么,显然不如hash表的
0
猜猜我是吧
猜猜我是吧
最快的就是hash,舍友去百度的时候被问了这个,但是,我觉得实际写代码应该不会用hash,毕竟hash只是用来查询不错,我觉得两个数组先分别排序,然后从队头开始一起向下搜,这样复杂度是2nlogn+2n,而hash是2n
猜猜我是吧
猜猜我是吧
回复 @hyjiacan : 嗯。。。所以hash是最快的,但是排序应该是最实用的
hyjiacan
hyjiacan
排序。。 这也是耗时的操作
0
d
de虫子
因为map中key不重复,  把两个数组放入map中,比较map的大小与两个数组的大小.
0
d
de虫子
public static boolean checkArrayIntercetion(String[] array1,String[] array2){
        Map<String,String> map=new HashMap<String,String>();
        String[] smallArray=array1.length>array2.length? array2:array1;
        String[] bigArray=array1.length> array2.length? array1:array2;
        int count=smallArray.length;
        for(String s:smallArray){
            map.put(s,s);
        }
        for(String s:bigArray){
            map.put(s,s);
            count+=1;
            if(count%100==0 && count>map.size()){
                return true;
            }
        }
        return count>map.size();
    }




0
d
de虫子

上面写的那个有问题. 应该是这样

public static boolean checkArrayIntercetion(String[] array1,String[] array2){
        Map<String,String> map1=new HashMap<String,String>();
        Map<String,String> map2=new HashMap<String,String>();
        String[] smallArray=array1.length>array2.length? array2:array1;
        String[] bigArray=array1.length> array2.length? array1:array2;
        for(String s:smallArray){
            map1.put(s,s);
        }
        int count=map1.size();
        for(String s:bigArray){
            map2.put(s,s);
        }
        for(String key:map2.keySet()){
            map1.put(key,key);
            count+=1;
            if(count%100==0 && count>map.size()){
                return true;
            }
        }
        return count>map.size();
    }



西夏一品堂
西夏一品堂
count%100==0 && count>map.size() 什么意思? 整个代码的思路是什么?
0
Will_awokE
Will_awokE
去看看 

Collections#disjoint()

返回顶部
顶部