如何高效查找区域层级中两个区域的最近公共上层区域（优化代码，避免双重循环）

当然有更高效的实现方式！不用双重循环也能快速找到两个区域的最近公共上层，这里有两种实用的方法，时间复杂度都能控制在O(M+N)（M、N分别是两个区域到顶层的路径长度），比暴力比对高效太多。

方法一：路径记录+单次遍历 #

这个思路是先把其中一个区域的所有上层（包括自身）记录到哈希集合里，再遍历另一个区域的上层路径——因为我们是从当前区域往顶层走，第一个匹配到的就是离两个区域最近的公共上层。

实现代码 #

AreaID Datastructures::common_area_of_subareas(AreaID id1, AreaID id2) {
    // 先校验两个区域是否存在
    auto area1_it = areas_.find(id1);
    auto area2_it = areas_.find(id2);
    if (area1_it == areas_.end() || area2_it == areas_.end()) {
        return NO_AREA;
    }

    // 收集第一个区域的所有上层（含自身）到哈希集合
    std::unordered_set<AreaID> area1_ancestors;
    const Area* current = &area1_it->second;
    while (current != nullptr) {
        area1_ancestors.insert(current->area_id_);
        current = current->upper_area_;
    }

    // 遍历第二个区域的上层，找第一个匹配的公共区域
    const Area* current2 = &area2_it->second;
    while (current2 != nullptr) {
        if (area1_ancestors.count(current2->area_id_)) {
            return current2->area_id_;
        }
        current2 = current2->upper_area_;
    }

    // 无公共上层（比如两个顶层区域不相同）
    return NO_AREA;
}

优势说明 #

• 逻辑简单直观，容易理解和维护；
• 时间复杂度O(M+N)，远优于双重循环的O(M*N)；
• 能处理所有边界情况：比如其中一个区域是另一个的上层、两个区域是同一个、无公共上层等。

方法二：深度对齐+同步遍历 #

如果想节省内存（不需要额外的哈希集合），可以用这个方法：先把两个区域的层级深度对齐，再同步往上遍历，直到找到第一个相同的区域。

实现代码 #

首先需要一个辅助函数计算区域的深度（从当前区域到顶层的步数）：

// 辅助函数：计算区域到顶层的深度（顶层区域深度为0）
int get_area_depth(const Area* area) {
    int depth = 0;
    const Area* current = area;
    while (current->upper_area_ != nullptr) {
        depth++;
        current = current->upper_area_;
    }
    return depth;
}

然后是核心函数：

AreaID Datastructures::common_area_of_subareas(AreaID id1, AreaID id2) {
    auto area1_it = areas_.find(id1);
    auto area2_it = areas_.find(id2);
    if (area1_it == areas_.end() || area2_it == areas_.end()) {
        return NO_AREA;
    }

    const Area* a = &area1_it->second;
    const Area* b = &area2_it->second;

    // 计算两个区域的深度
    int depth_a = get_area_depth(a);
    int depth_b = get_area_depth(b);

    // 对齐深度：把较深的区域往上移动，直到和另一个区域深度相同
    while (depth_a > depth_b) {
        a = a->upper_area_;
        depth_a--;
    }
    while (depth_b > depth_a) {
        b = b->upper_area_;
        depth_b--;
    }

    // 同步往上遍历，找到第一个公共区域
    while (a != nullptr && b != nullptr && a->area_id_ != b->area_id_) {
        a = a->upper_area_;
        b = b->upper_area_;
    }

    // 返回结果：找到则返回ID，否则返回NO_AREA
    return (a != nullptr && b != nullptr) ? a->area_id_ : NO_AREA;
}

优势说明 #

• 空间复杂度O(1)，不需要额外存储路径；
• 同样是O(M+N)的时间复杂度，适合内存敏感的场景；
• 避免了哈希集合的构造开销，在路径较长时性能表现更稳定。

注意事项 #

1. 一定要先判断upper_area_是否为nullptr，避免空指针访问崩溃；
2. 两种方法都能正确处理直接/间接上层的情况，且自动选择最近的公共区域；
3. 如果两个区域本身是同一个，方法会直接返回自身ID，符合需求。

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