慕课联盟网站开发实战/南宁今日头条最新消息
这是来自腾讯2014年软件开发笔试题： A，B两个整数集合，设计一个算法求他们的交集，尽可能的高效。
一、第一种算法，暴力求解，直接采用遍历或者枚举的方法，这种办法最简单易想，但是时间复杂度比较高，为
O(n^2),这是最复杂的情况。
二、预处理。其实思想和C语言中的预处理一样，对数据记性归一化处理。说白了，就是对数组先进行排序。数组排序的算法时间复杂度最低是O(nlogn)，数量级已经低于第一种算法的时间复杂度。
例如已经排序好的两个数组A，B，使用下列伪代码进行判断交集：
int Find()
{
result=i=j=0;
while(i
{
if(a[i]
i++;
else if(a[i]>b[j])
j++
else
result++;
}
return result;
}
时间复杂度为O(n),综合排序的时间复杂度则整体复杂度为：O(nlogn)
三、计数排序。也就是把两个数组A和B都遍历到一个新的数组里，然后在统计重复的数字即可，这个时间复杂度就是O(n)。当然，计数排序是有条件的，也就是要求数组内数字的范围是已知并且不是很大，否则使用这种办法得不偿失。
四、根据算法三应该大家能够想到用哈希函数或者哈希表来解决问题。也就是将数组A哈希到哈希表中，然后继续将数组B哈希到哈希表中，如果发生哈希碰撞则统计加1，最后可以得出数组的交集。时间复杂度也就是哈希所有元素的复杂度O(n)。
一、第一种算法，暴力求解，直接采用遍历或者枚举的方法，这种办法最简单易想，但是时间复杂度比较高，为
O(n^2),这是最复杂的情况。
二、预处理。其实思想和C语言中的预处理一样，对数据记性归一化处理。说白了，就是对数组先进行排序。数组排序的算法时间复杂度最低是O(nlogn)，数量级已经低于第一种算法的时间复杂度。
例如已经排序好的两个数组A，B，使用下列伪代码进行判断交集：
int Find()
{
result=i=j=0;
while(i
{
if(a[i]
i++;
else if(a[i]>b[j])
j++
else
result++;
}
return result;
}
时间复杂度为O(n),综合排序的时间复杂度则整体复杂度为：O(nlogn)
三、计数排序。也就是把两个数组A和B都遍历到一个新的数组里，然后在统计重复的数字即可，这个时间复杂度就是O(n)。当然，计数排序是有条件的，也就是要求数组内数字的范围是已知并且不是很大，否则使用这种办法得不偿失。
四、根据算法三应该大家能够想到用哈希函数或者哈希表来解决问题。也就是将数组A哈希到哈希表中，然后继续将数组B哈希到哈希表中，如果发生哈希碰撞则统计加1，最后可以得出数组的交集。时间复杂度也就是哈希所有元素的复杂度O(n)。