javascript集合求交集

两集合求交集

思路：

1. 每一次从B数组中取一值，然后在A数组里逐个比较，如果有相等的，则保存。该算法复杂度为 O(MN). M, N 分别为数组 A B 的长度。

2. 因为A B 都排过序，所以，每一次从B数组取值后，可以利用二分查找看是否在数组A里有B所对应的值，这样复杂度变成了O(N lg M)。 这里，如果N 比 M 大，可以从A中取值，然后在B中判断是否有A的值，这样，复杂度为  O(M lg N)。

3. 利用hashtable. 先把A中的值存在hashtable里，然后对于每一个B中的值，判断是否在A中存在，因为hashtable查找的平均复杂度为 O(1), 所以，整个算法复杂度为O(N), 但是，这里的空间复杂度为 O(M) 。但是，这种方法适合数组比较小的情况。因为如果A数组比较大，hashtable会出现collision的情况，这样，查找的平均复杂度就不再是 O(1)。

方法1：

首先对2个数组排序，然后对arr1的元素都在arr2中进行二分查找。

刚开始写二分查找代码：

function binarySearch(arr,key)
{
    var low,high,mid;
    low=0;
    high=arr.length-1;
    while(low<=high)
    {
        mid=parseInt((low+high)/2);
        if(arr[mid]==key)
        {
            return mid;
        }
        else if(arr[mid]<key)
        {
            low=mid+1;
        }
        else
        {
            high=mid-1;
        }
    }
    return -1;
}测试时var a=[1,2,3,5,7];

 测试时var a=[1,2,3,5,7];
var result=binarySearch(a,7);
 console.log(result)

3可以得到正确结果2，其他的都返回-1，为什么？调试时发现

如查找1时，

(0+4)/2=2;

a[2]=3>key; high=1;

mid=(0+1)/2 不为0，而是0.5;

导致错误。

原来2个数相除，要得到整数，必须用相关函数，使用parseInt还是Math.floor()参考：http://stackoverflow.com/questions/8170865/math-round-vs-parseint

http://zhidao.baidu.com/question/495738802.html

一个比较好的回答：

The two functions are really quite different.

parseInt() extracts a number from a string, e.g.

parseInt('1.5')// => 1 返回一个number类型

Math.round() rounds the number to the nearest whole number:

Math.round('1.5')// => 2 返回的是一个number类型。

parseInt() can get its number by removing extra text, e.g.:

parseInt('12foo')// => 12

However, Math.round will not:

Math.round('12foo')// => NaN

Basically, you should probably use both since you're getting input from the user:

var number = parseInt(prompt('Enter number:'));var rounded =Math.round(number);

我们用Math.floor.改后的代码为：

function binarySearch(arr,key)
{
    var low,high,mid;
    low=0;
    high=arr.length-1;
    while(low<=high)
    {
        mid=Math.floor((low+high)/2);
        if(arr[mid]==key)
        {
            return mid;
        }
        else if(arr[mid]<key)
        {
            low=mid+1;
        }
        else
        {
            high=mid-1;
        }
    }
    return -1;
}

如何对一个数组排序？

arrayObject.sort(sortby)
我最开始写的代码为：
var b=[2,3,4,8,9,10];

for(var i=0;i<b.length;i++)
　　console.log(b[i]);

发现输出的是:10 2 3 4 8 9  

为什么？以前没怎么用过sort函数。不清楚怎么回事.去w3cshool查了一下：

arrayObject.sort(sortby)

参数	描述
sortby	可选。规定排序顺序。必须是函数。

返回值

对数组的引用。请注意，数组在原数组上进行排序，不生成副本。

说明

如果调用该方法时没有使用参数，将按字母顺序对数组中的元素进行排序，说得更精确点，是按照字符编码的顺序进行排序。要实现这一点，首先应把数组的元素都转换成字符串（如有必要），以便进行比较。

如果想按照其他标准进行排序，就需要提供比较函数，该函数要比较两个值，然后返回一个用于说明这两个值的相对顺序的数字。比较函数应该具有两个参数 a 和 b，其返回值如下：

• 若 a 小于 b，在排序后的数组中 a 应该出现在 b 之前，则返回一个小于 0 的值。
• 若 a 等于 b，则返回 0。
• 若 a 大于 b，则返回一个大于 0 的值。

当函数返回值为大于0的时候就交换两个数组项的顺序，否则就不交换。

  function desc(x,y) 
    ...{ 
        if (x > y)   
            return -1; 
        if (x < y)           
            return 1; 
    } 
    function asc(x,y) 
    ...{ 
        if (x > y)   
            return 1; 
        if (x < y)           
            return -1; 
    } 
    arrA.sort(desc);    // sort by desc 
    document.writeln(arrA); 
    document.writeln("<br>"); 
    arrA.sort(asc);    //sort by asc 
    document.writeln(arrA);
//输出结果：
6,5,4,3,2,1 
1,2,3,4,5,6 

这个恰好是与c++是相反的。

在本例中，我们将创建一个数组，并按字母顺序进行排序：
<script type="text/javascript">

var arr = new Array(6)
arr[0] = "10"
arr[1] = "5"
arr[2] = "40"
arr[3] = "25"
arr[4] = "1000"
arr[5] = "1"

document.write(arr + "<br />")
document.write(arr.sort())

</script>
输出：
10,5,40,25,1000,1
1,10,1000,25,40,5

可以看到，不用参数，默认是按字典顺序排列的。我们的

var b=[2,3,4,8,9,10];
虽然里面元素不是字符串，也是按照字符串对待按照字典顺序排列，所以出现了:
10 2 3 4 8 9 .
请注意，上面的代码没有按照数值的大小对数字进行排序，要实现这一点，就必须使用一个排序函数：

function sortNumber(a,b)
{
return a - b
}

var arr = new Array(6)
arr[0] = "10"
arr[1] = "5"
arr[2] = "40"
arr[3] = "25"
arr[4] = "1000"
arr[5] = "1"

document.write(arr + "<br />")
document.write(arr.sort(sortNumber))

</script>
输出：
10,5,40,25,1000,1
1,5,10,25,40,1000

以前还没注意到document.write可以直接输出一个array，这个很方便，要记住。

字符串的排序函数是：

function sortNumber(a,b)
{
return a - b
}
如何是数值也是一样的。

完整求交集代码：

function binarySearch(arr,key)
{
    var low,high,mid;
    low=0;
    high=arr.length-1;
    while(low<=high)
    {
        mid=Math.floor((low+high)/2);
        if(arr[mid]==key)
        {
            return mid;
        }
        else if(arr[mid]<key)
        {
            low=mid+1;
        }
        else
        {
            high=mid-1;
        }
    }
    return -1;
}

var a=[1,2,3,5,7];
var b=[2,3,4,8,9,10];
 
function sortNumber(a,b)
{
    return a-b;
}
 
a.sort(sortNumber);
b.sort(sortNumber);
 
    
for(var i=0;i<a.length;i++)
{
     if(binarySearch(b,a[i]) != -1) 
         console.log(a[i]);
}

此复杂度为M*log2N.

方法2：

for(var i=0,lenA=a.length,j=0,lenB=b.length;i<lenA&& j<lenB;)
{
    if(a[i]==b[j])
    {
        document.write(a[i]+"<br/>");
        i++;
        j++;
    }
    else if(a[i]<b[j])
    {
        i++;
    }
    else
    {
        j++;
    }
}

这个算法的排序后的复杂度M+N.（不算sort）。

附上:  常用的javascript集合操作:  http://4umi.com/web/javascript/array.php

 c++集合求交集，并集：

#include <iostream>  
  
#include <algorithm>  
#include <iterator>  
  
#include <vector>  
using namespace std;  

void vectorJiaoJi(const vector<int>& v1,const vector<int>& v2,vector<int>& des)
{
    int i=0,j=0;//定位2个有序向量的头部
    des.clear();
    while(i<v1.size()&&j<v2.size())
    {
        if(v1[i]<v2[j])
            i++;
        else if(v1[i]==v2[j])
        {
            des.push_back(v1[i]);
            i++;
            j++;
        }
        else
            j++;
    }
}

void vectorBingJi(const vector<int>& v1,const vector<int>& v2, vector<int>& des)
{
    int i=0,j=0;
    des.clear();
    while(i<v1.size()&&j<v2.size())
    {
        if(v1[i]==v2[j])
        {
            des.push_back(v1[i]);
            i++;
            j++;
        }
        else if(v1[i]<v2[j])
        {
            des.push_back(v1[i]);
            i++;
        }
        else
        {
            des.push_back(v2[j]);
            j++;
        }
    }


        //对于部分未能压入vector元素，继续操作
        while(i<v1.size())
        {
            des.push_back(v1[i]);
            i++;
        }
        while(j<v2.size())
        {
            des.push_back(v2[j]);
            j++;
        }
}
int main()
{

     vector<int> v1;  
        vector<int> v2;  
        vector<int> des;  
         
        v1.push_back(5);  
        v1.push_back(7);  
        v1.push_back(9);  
        v1.push_back(12);  
        v1.push_back(15);  
        v1.push_back(20);  
        v1.push_back(28);  
         
        v2.push_back(10);  
        v2.push_back(11);  
        v2.push_back(12);  
        v2.push_back(13);  
        v2.push_back(14);  
        v2.push_back(15);  
        v2.push_back(19);  
  

        sort(v1.begin(),v1.end());
        sort(v2.begin(),v2.end());  

        vectorJiaoJi(v1,v2,des);  
        int i=0;  
        while(i< des.size())  
        {cout<<des[i]<<endl;i++;}  
        cout<<endl;  
         
        vectorBingJi(v1,v2,des);  
        i=0;  
        while(i< des.size())  
        {cout<<des[i]<<endl;i++;}  
        cout<<endl;  
}