这是来自腾讯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)。