两集合求交集
思路：
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://*.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')// => 12However, Math.round will not:
Math.round('12foo')// => NaNBasically, 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=,j=;//定位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=,j=;
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();
v1.push_back();
v1.push_back();
v1.push_back();
v1.push_back();
v1.push_back();
v1.push_back(); v2.push_back();
v2.push_back();
v2.push_back();
v2.push_back();
v2.push_back();
v2.push_back();
v2.push_back(); sort(v1.begin(),v1.end());
sort(v2.begin(),v2.end()); vectorJiaoJi(v1,v2,des);
int i=;
while(i< des.size())
{cout<<des[i]<<endl;i++;}
cout<<endl; vectorBingJi(v1,v2,des);
i=;
while(i< des.size())
{cout<<des[i]<<endl;i++;}
cout<<endl;
}