18
回答
[面试题]如何快速的判断两个数组是否有交集
public boolean hasIntersection(String[] array1, String[] array2)
{
     ...
}


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

求最快的方法



<无标签>
举报
共有18个答案 最后回答: 3年前
arr2 join 使用特定字符成字符串,然后遍历arr1,在字符串中找arr1的元素。
--- 共有 1 条评论 ---
maosiarr1[0] = "a,b"; arr2[0] = "a"; arr2[1] = "b"; 这种情况下不行 3年前 回复

引用来自“God20134”的评论

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




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

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();
    }



--- 共有 1 条评论 ---
西夏一品堂count%100==0 && count>map.size() 什么意思? 整个代码的思路是什么? 3年前 回复
顶部