两个超大数组求交集
哪些公司问过
答案要点
- 哈希分桶:同一哈希把两集合分桶,相同元素必在同号桶中,逐对求交再合并
- 外部排序后双指针归并扫描
- 位图:数值范围有限时标记一个集合再扫描另一个,32 位整数约 512MB
- 布隆过滤器先排除不存在的元素,再精确验证;更大数据用 MapReduce
- 有序时双指针 O(m+n);一大一小时对小集合元素在大集合里二分
易错点
- 默认数据能放进内存
- 两集合用不同的哈希函数分桶
- 只用布隆过滤器而不做精确验证
面试官常见追问
- 两个集合有序时怎么求交集?
- 为什么哈希分桶能保证正确?
- 布隆过滤器为什么还要精确验证?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。