【有趣的面试算法题】之五 各种整数集的处理，求交集可用双重映射，省空间易扩展无冲突
基本题型
基本题： A、B两个整数集合，设计一个算法求他们的交集，尽可能地高效。
这样一个面试题目，像是比较经典，经常得以讨论，大家也热情地给出了好久解法。在2014年腾讯校园招聘中它又出现了，无疑地又平添了大家对它的研究热情，当然也包括我！
目前大家比较认可的方法是，进行映射，以空间换时间。 但具体的映射方法又有好几种：
一，直接按值映射。申请两片足够大的空间，按其绝对值进行标识。这是使用最简单的HASH方法，空间浪费也是巨大的，但绝对不会有冲突。
二，多重HASH映射。相对方法一，节省了很多空间，但不可能避免地会有冲突。 至于具体如何构造这种映射方法/函数，则没有多少阐述。
为能集约地使用空间，又倾向于采用bitmap等数据结构保存标志。
当然，以上均假设AB数据集中元素是没有重复的。所以，如果数集有重复数据出现的话，类似的题目又有了。例如：在一个整数集中数字中，求出现且只出现一次的子集、求出现次数不少于两次的子集、求出现次数超过一半的子集、求中位数....
如果数集中只有一个数只出现一次，其余的均是出现两次，如何快速找出？
【由于条件较特殊，可以不用映射，采用特殊方法：全部数据参与异或之后所得就是目标数】
还有一些变化题型：
一,A、B两个区间集合，求交集。 单个的数值演变成了一个区间，并且一个集合内部的区间还有可能重叠。
二, A为一维数轴上N点的增序集合，求长为L的尺子最多能覆盖多少个点。【2014百度校园招聘研发类题目】
三, 数组中的最大子序列的和 / 积
四，...
现还是回到最初的基本题，我的一个可以实现 “零冲突”的双重HASH映射思路是：
一，将整数以字符串形式表示，正负分别处理
二，双重映射方法。
1、按位数映射：比如，六位数的进入六位数的映射空间，五位的进五位
2、按位值映射：个、十、百、千、万...上的数字直接按值映射
三，将数集A用于构造映射表，数集B用于查验。
四，构造方法。预设数值的最大长度为N， 则需要申请大小为2*(1+N)*N/2*10空间，并初始化为0，然后逐一映射，映射到的位置值置为1。
五，查验方法。一个数的所有映射位都为1时，“说明这个地方之前有人来过”，那么这个数即可进入交集序列。
相对于直接按值映射，优点有：
一，省空间：以32位的整数为例，直接型所需要的空间为65536，我的双重映射需要(1+5)*5*10=300，仅需要原来的300/65536=0.46%！！
二，易扩展：比如数值超过64位呢？ 超过6400位呢？ 呵呵，直接的整数类型不支持了吧？
