前两天面某大厂，有这么一条考数据结构的题，属实把我难倒了，要考虑的点实在太多了。

题目基本如下：

1. 有n个集合，每个集合里面存放无规律数字，每个集合可以认为是从一个文件里面读出来的数字，自己考虑用什么数据结构来存。（一个集合里面是不允许有重复元素的）
2. 求两个集合的并集、交集、子集。（子集即两个集合的交集的一部分，例如sub(a&b,0)就是求a、b两个集合的交集的子集，子集大小为10）
3. 求多个集合的并集、交集、子集。
4. 求多个集合进行并集、交集混合运算后的子集。（例如，sub((a|b|c|)&(d|f|g),100)代表a、b、c三个集合的并集和d、f、g三个集合的并集的交集的子集。子集长度为100）.

问题一：把这些集合存成什么数据结构呢？

哈希表（不行）

• 一开始，我想的是使用哈希表来存，这样可以快速定位，然后求并交集的时候，遍历一个集合的元素 i ，用 i 来判断另一个元素的集合是否存在 i 就可以得到交集了，并集和这个也基本是同理的。
• 缺点：
  • 哈希表占用空间太大
    • 第一：有空余的桶没有用；
    • 第二：java的哈希表实现HashSet的value是一个final的Object。又占一部分空间
• 所以哈希表肯定不能用。

位图（不行）

• 把集合的数据存到位图。虽然位图可以减少空间的占用，但题目没有说数字的范围，所以，有可能会存得非常散。时间复杂度和空间复杂度都会非常高。

数组（可行）

• 毫无疑问，数组是占用空间最小的数据结构了。
• 但是，在当前场景怎么利用数组呢？难道求交集的时候，双指针来进行判断遍历吗？这样时间复杂度将会是O(n^2).
• 所以，我们会考虑一个优化，就是在存入数组时，先把集合里面的元素进行排序

• 排序？排序有什么用呢？在当前场景下，排序发挥到了什么作用呢？

问题二：求两个集合的交集、并集

求交集

1. 避免走回头路。假设求交集，现在有两个有序数组A和B，分别有两个指针a和b指向它们的头一个元素。首先固定a指针，让b指针移动，找到适合a元素待的地方（相等或者在两个元素之间）。
   1. 如果是相等的话，就把a元素加入到结果集。a指针继续移动到下一位。
   2. 然后，b指针也是向右移动就可以了。因为左边的肯定是小的，不需要理会了。
   3. 

    时间复杂度为O(n+m)，n和m为A和B数组的长度。

2. 二分查找。b指针的移动还是有讲究的，如果每次都移动一步去遍历找适合a元素的位置的话，那么就是O(n)，假如我们使用二分查找来优化这个过程，那么时间复杂度将会是O(logn)。

时间复杂度变成了O(n+logm)

求并集

求并集也是同理。

1. 固定a指针，用bPrev保存b上一次的值，然后b指针二分查找找到B数组内a可以待的地方，一下子把bPrev到b的所有值加到结果集合。
2. 然后添加一下a元素，判一下重，a指针继续向前移动。
3. 这样重复，就可以得到有序的并集。

时间复杂度一样是O(n+logm)

求子集

这个就更简单了，就是求交集的一部分，找够需要的个数，就提前结束运算就行。

问题三：求多个集合的交集、并集、子集。

首先做简单的。

求多个集合的交集。a&b&c

二分查找

• 首先我们要知道，对于多个集合来说，交集，就是每一个集合里面都得有的元素。
• 所以，很明显，我们只需要找出最小的那个集合A，然后遍历集合的每一个元素a，然后用二分查找在其它集合里面找：
  • 如果在集合B找到就继续找下一个集合C，以此类推。
  • 如果在集合B里面找不到，那么a指针就得往前移了。
• 最后得到一个有序的交集。

求多个集合的并集。a|b|c

• 很多人一开始就会想，并集不就是把所有的都加入结果集，就可以了吗？
• 其实不然，因为有可能有重复的。那我们就用HashSet存不就行了？不就可以去重了？
• 其实不然，首先HashSet占的空间大，而且用HashSet还有一个致命的弱点，它里面的元素是无序的。
• 为什么要结果集一定要有序的？
  • 我们就需要看问题4了，假如是求sub((a|b|c)&(d|f|g),2)。
  • 我们就需要先计算两个并集，然后计算两个并集的交集，这又回到问题二了，就是求两个集合的交集，所以，我们还是需要两个集合是有序的，才能像问题二那样解决问题。
  • 也就是说，求出的并集也一定是有序的，才能用上问题二的算法。
• 所以，问题又变为了“如何用多个有序数组合并成为一个有序数组？”
• 对，就是堆排序。

方式一：把所有的有序数组都加入到堆里面，然后，每次把头节点弹出，就可以得到有序数组。弊端：使用的临时空间为所有元素数量O(N*M)的大小，并且每次建堆、弹节点都得走O(logN*M)个交换，也就是堆太大了。

方式二：

1. 一开始，每个有序数组有一个指针指向第0个元素，然后把所有第0个元素加到堆。
2. 然后弹出一个元素A[i]，加到结果集。
3. 然后，把A[i+1]添加到堆里面。
4. 重复2和3步骤即可。

这样，堆就变小了。

• 那么问题又来了。怎么去重呢？
  1. 首先，我们知道：需要弹出的时候，那么弹出的就是最小的。
  2. 如果有两个相同的元素A和B，在A需要弹出的时候，那么下一个要弹出的就是B，因为每次都是弹出最小的。
  3. 所以，我们在弹出时，判断和结果集里面的最后一个比较一下，如果重复，就不放进结果集就可以了。

求多个集合的交集、并集的子集

这个就比较简单了，找够数量就终止上面的计算就可以了。

问题四：组合运算

这个也没有太多好谈的，因为我们的问题3就是为了问题4服务的。因为，我们问题3得到的交集和并集都是有序的，所以，运用问题2的操作方法就可以解决。

这场面试总共面了2个小时，单单这个问题就和面试官扯皮了1个多小时，面试官人还是挺好的，一直在引导我思路，最后还给我过了，属实感谢这个面试官。