两个整数集合最快算法求交集_F_hawk189_新浪博客

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