面试题库 › 算法 / 大模型 › 并查集实现:路径压缩与按秩合并

并查集实现:路径压缩与按秩合并

难度 ★★☆在 2 场真实面经中被问到 方向:算法 / 大模型考点:图论

哪些公司问过

华为1拼多多1

常见岗位:AI 应用 / Agent 开发

答案要点

  1. 初始化:parent[i]=i,size 初始化为 1 或 rank 初始化为 0
  2. find 路径压缩:把路径上节点直接指向根,或迭代路径减半
  3. union 按秩/按大小合并:小树根挂到大树根下,并更新 size/rank
  4. 两者结合后均摊复杂度 O(α(n)),近似常数
  5. 可维护连通分量数;数据量大时用迭代 find 防栈溢出

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题