并查集的原理与实现
哪些公司问过
商汤1多家公司(猿辅导、百度、网易互娱、滴滴、锐捷网络、吉比特、亿联网络等)1
答案要点
- 维护不相交集合,支持查找所属集合与合并,常用于连通性判断
- parent 数组记录父节点,根节点代表集合
- 查找:沿父节点找到根,用路径压缩把沿途节点直接指向根
- 合并:找到两个根,按秩或按大小把小树挂到大树下
- 两者结合后均摊时间接近常数(反阿克曼函数级别)
易错点
- 不做路径压缩,退化成链表
- 合并时直接合并两个元素而不是它们的根
- 递归路径压缩在深度很大时栈溢出
面试官常见追问
- 并查集能解决哪些问题?
- 路径压缩可以写成迭代吗?
- 并查集支持删除吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。