两个集合，求它们的交集 - Gukie/interview GitHub Wiki

最原始的题目应该是网易的笔试题：

给定两个整数集合A和B，每个集合都包含20亿个不同整数. 求A跟B集合的交集; 要求：可以使用外存，但内存的使用不能超过4GB

答案:

  1. 使用BitSet实现

  2. 分别遍历集合A和B，对里面的每个元素，都对10 取模 (n%10),然后存储到不同的文件中， 比如A集合的文件名是： a0, a1... B集合的文件名是： b0, b1...

  3. 这样可以确定，文件下标一样的，才有可能有交集，即 a0跟b0 可能存在交集，但 a0跟b1不可能存在交集

  4. 然后对 每对文件，进行处理，比如 a0跟b0

  1. 将a0的数据读取到 一个BitSet - bs1
  2. 将b0的数据读取到 另个一个BitSet - bs2
  3. 对bs1进行遍历，如果元素是 1，则取bs2中的相应下标，看是否也是1， 如果是，则属于交集部分的
  4. 同样的，对bs2也遍历一次
  5. 由于BitSet底层是用long的数组实现的，所以，通过下标获取对应元素的时间复杂度是O(1), 所以不怎么耗时
  6. 这样两次遍历，就可以求得交集了

refer:

  1. http://www.cnblogs.com/hellogiser/p/ab-set-intersection.html
  2. http://www.cnblogs.com/sooner/p/3280050.html