js 数组求交集

现有字符串两个，求字符串的共同值。（如果字符串长度大于1万）
例：//轻量级
var str1="a;b;c;d;e;f;g;h;";
var str2="e;h;k;m;l;";
//经过运算求的交集
var str3="e;h";//重量级
var str1="";
var str2="";
var str3=""
for(var i=0;i<10000;i++){
   str1=i+";";
}
for(var i=8000;i<20000;i++){
   str2=i+";";
}
//var str3=....求一算法，谢谢。

解决方案 »

  1.   


    var str1="a;b;c;d;e;f;g;h;";
    var str2="e;h;k;m;l;";
    var getCross=function(a,b) {
        if(a.length>b.length) {//a长度大于b时交换，应该能提高效率
            var temp=b,b=a,a=temp;
        }
        var reg=a.replace(/;/g,"|").replace(/\|$/,"");//构造正则，并去掉结尾的|
        return b.match(new RegExp(reg,"g"));
    }
    alert(getCross(str1,str2));
      

  2.   


    var str1="a;b;c;d;e;f;g;h;";
    var str2="e;h;k;m;l;";
    var getCross=function(a,b) {
        if(a.length>b.length) {//a长度大于b时交换，应该能提高效率
            var temp=b,b=a,a=temp;
        }
        var reg=a.replace(/;/g,"|").replace(/\|$/,"");//构造正则，并去掉结尾的|
        return b.match(new RegExp(reg,"g")).join(";");//用分号连接
    }
    alert(getCross(str1,str2));
      

  3.   


    var tmpArr = (str1+str2).split(""),result = [];
    tmpArr.sort();
    var i=tmpArr.length-1;
    while(i>=0){
    if(tmpArr[i]!=tmpArr[--i]){
    tmpArr.pop();
    }else{
    result.push(tmpArr.pop());
    }
    if(i)
    break;
    }
    str3 = result.join("");
      

  4.   


    在小数据情况下灰常不错，赞一个！你这段会有BUG，假设数组A或B有重复，而另一数组中并未包含此数据，则结果是错的，而且，你使用了排序（还没用高效排序），所以还有改进的空间。
      

  5.   

    这样说不妥，如果是线性的，更大都没问题。大数组情况下，貌似比较好的方式就是空间换时间了，参考：
    <script type="text/javascript">
    var str1 = "a;b;c;d;e;f;g;h;",str2 = "e;h;k;m;l;";
    var a1 = str1.split(';'),a2 = str2.split(';'),l1 = a1.length-1,l2 = a2.length-1;
    var ret = [],tmp = {},ta,tb;for(var i=0;i<l1;i++){
        ta = a1[i];
        if(ta in tmp){if(tmp[ta]==2){ret.push(ta);}continue;}
        tmp[ta] = 1;
    }for(i=0;i<l2;i++){
        tb = a2[i];
        if(tb in tmp){if(tmp[tb]==1){ret.push(tb);}continue;}
        tmp[tb] = 2;
    }tmp = null;alert('交集数：'+ret.length+'\n'+ret);
    </script>
    期待更好的算法！
      

  6.   

    连续系统函数调用版
    <script type="text/javascript">
    var a1=[],a2=[];
    var str1,str2,str3;for(var i=0;i<10000;i++){
       a1.push(i);
    }for(var i=8000;i<20000;i++){
       a2.push(i);
    }str1=a1.join(";");
    str2=a2.join(";");
    var reg=/(;\d+)(\1)+/g;
    str3=";"+(str1+";"+str2)
    .split(";")
    .sort(function(o1,o2){return o1*1>o2*1?1:-1;})
    .join(";")
    .match(reg)
    .join("")
    .replace(reg,"$1");document.write(str3.replace(/;{2,}/g,""));</script>
      

  7.   

    貌似楼上的效率也不行，而且有局限性，另外仍然存在3 楼 inpool 代码中的BUG - -!
      

  8.   

    <html>
    <head>
    <script tpye='text/javascript'>var len = 4;
    var hig = 3;var temar = new Array();
    for(var i=0;i<hig;i++)
    {
    temar[i] = new Array();
    }temar[0][0] ="3";
    temar[0][1] ="4";
    temar[0][2] ="7";
    temar[0][3] ="8";temar[1][0] = "5";
    temar[1][1] ="4";
    temar[1][2] ="8";temar[2][0] = "8";
    temar[2][1] = "5";
    temar[2][2] = "3";//将最短的数组拿来匹配
    var compare = new Array();
    compare =temar[0];
    for(var i =0;i<temar.length;i++)
    {
     if(temar[i].length < compare.length)
    {
    compare = temar[i]
    }
    }
    //判断
    for(var i=0;i<compare.length;i++)
    {
    for(var z=0;z<temar.length;z++)
    {
    var bl = 0;
    for(var j=0;j<temar[z].length;j++)
    {
    if(temar[z][j] != compare[i])
    {
    bl++;
    }
    }
    if(temar[z].length == bl)
    {
    compare[i]=null;
    }
    }
    }
    alert(compare.join(":"));</script>
    </head>
    <body>
    </body>
    </html>
    菜鸟写一个玩玩