如何高效查找用户列表中两位用户的最低共同经理

核心思路 #

针对海量用户数据，最优方案是通过哈希表（字典）预处理+溯源路径对比替代树结构遍历，把每次查询的时间复杂度降到O(d)（d为用户层级深度，远小于总用户数n）。

具体步骤 #

1. 预处理生成映射表
   将用户数组转换成用户→直接经理的哈希表，预处理时间复杂度O(n)，后续查询直接经理的时间为O(1)。
   示例代码（JavaScript）：

   const userToManager = new Map();
   // 假设users是你的用户对象数组
   users.forEach(userObj => {
     userToManager.set(userObj.User, userObj.Manager);
   });
   

2. 生成第一个用户的经理链集合
   从目标用户A的直接经理开始，向上遍历所有层级的经理并存入集合，时间复杂度O(d₁)（d₁为用户A的经理链长度）。

3. 遍历第二个用户的经理链找交集
   从目标用户B的直接经理开始向上遍历，每遇到一个经理就检查是否在用户A的经理链集合中，第一个匹配到的就是最低共同经理，时间复杂度O(d₂)（d₂为用户B的经理链长度）。

示例验证 #

以你给出的用户数组为例：

• 查找Ben和Steve的最低共同经理：
  • Ben的经理链：John → Jake
  • Steve的经理链：John → Jake
  • 遍历Steve的经理链时，第一个出现在Ben经理链集合中的是John，符合预期。
• 查找Ben和John的最低共同经理：
  • Ben的经理链：John → Jake
  • John的经理链：Jake
  • 遍历John的经理链时，第一个匹配的是Jake，符合预期。

方案优势 #

相比树结构方案：

• 预处理仅需O(n)时间，远低于构建树结构的成本；
• 每次查询仅需遍历两个用户的经理链，无需遍历整个树，在用户层级较浅的场景下效率极高；
• 哈希表的查询时间为O(1)，避免了树结构中查找节点的O(n)或O(logn)开销。

边界情况处理 #

• 若其中一个用户是顶层管理者（无经理），则不存在共同经理，可返回null或根据业务需求处理；
• 若两个用户的经理链完全无交集（需考虑数据异常场景），同样返回null。

内容的提问来源于stack exchange，提问作者AkanshaM