C++ 中查找最小公共区域

2025年2月11日 | 阅读 12 分钟

引言

分层结构在自然和人造系统中都普遍存在，代表了实体之间的嵌套关系，例如地理区域、组织层级、文件系统和生物分类。在计算机科学和数据管理中，高效地导航这些结构对于查询数据、管理资源和理解关系等任务至关重要。在这些结构中，一个常见的问题是在两个给定节点之间找到最小的公共区域。

这个问题可以使用 C++ 来有效解决，因为它拥有强大的数据结构和算法。解决方案涉及一种称为父节点映射和祖先追踪的方法。首先，构建一个父节点映射，其中每个区域都映射到其父节点，从而方便在层级结构中快速向上遍历。接下来，通过从每个节点向上移动到根节点来追踪两个给定区域的祖先，并存储遇到的所有祖先。最后，通过识别两个区域追踪路径中的第一个公共祖先来找到最小的公共区域。

在 C++ 中使用 unordered_map 进行父节点映射，使用 unordered_set 进行祖先追踪，可以确保高效的存储和检索，利用平均 O(1) 的查找时间复杂度。这种方法模仿了追踪血统或报告结构的自然过程，使其既直观又健壮，能够处理现实世界应用中的各种分层结构。

现实世界中的分层结构

地理区域

地理区域的划分方式体现了分层结构的明显特征。从最广泛的层面开始，地球被划分为大陆，如“北美洲”和“南美洲”。在这些大陆内部，进一步细分。例如，“北美洲”包含“美国”和“加拿大”等国家。“美国”又被划分为州，这些州又被细分为市和镇。这种嵌套层级结构可以清晰、有序地表示地理数据，便于导航、管理和区域规划。

组织图

在公司中，公司使用分层结构来组织其劳动力。该层级的顶端是首席执行官，其次是高级行政人员、中层经理，最后是普通员工。这种结构明确了汇报关系，界定了角色和职责，并有助于资源管理。它允许有效的沟通、任务委派和战略规划。通过了解组织层级，员工可以更有效地履行自己的职责，领导者可以更有效地管理公司。

文件系统

计算机上的文件系统是固有的分层结构。它们由包含子目录和文件的目录组成。例如，根目录可能包含“Documents”、“Pictures”和“Videos”等文件夹。“Documents”中可能包含“Work”和“Personal”等子文件夹，每个子文件夹都可以包含各种文件。这种分层组织支持高效的数据存储、检索和管理。它允许用户系统地查找和管理文件，为组织数字信息提供清晰的结构。

生物分类

在生物学中，使用分层结构来对生物进行分类。称为林奈分类法的分类系统，从界和门等广泛的类别开始，缩小到纲、目、科、属和种。例如，域“真核生物”包括界“动物界”，后者进一步包括门“脊索动物门”，纲“哺乳纲”，目“灵长目”，科“人科”，属“人属”，种“智人”。这种层级结构帮助生物学家理解进化关系，追踪谱系，并有效地组织生物数据。

方法一：父节点映射和祖先追踪法

父节点映射和祖先追踪法是一种用于在分层结构中查找两个给定节点之间的最小公共区域（或最近公共祖先）的方法。该方法对于树和分层数据结构特别有效，其中每个节点（区域）都有一个唯一的父节点，允许我们高效地从任何节点向上追踪到根节点的路径。

程序

 
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <string>
using namespace std;
// Define a structure for holding region data
struct Region {
    string name;
    vector<Region*> children;
    // Constructor to initialize a region with a name
    Region(string n) : name(n) {}
};
//Function to build a hierarchical structure and return the root node
Region* buildHierarchy() {
    // Initialize regions
    Region* earth = new Region("Earth");
    Region* na = new Region("North America");
    Region* us = new Region("United States");
    Region* ca = new Region("Canada");
    Region* ny = new Region("New York");
    Region* caState = new Region("California");
    Region* losAngeles = new Region("Los Angeles");
    Region* sanFrancisco = new Region("San Francisco");
    Region* ontario = new Region("Ontario");
    Region* quebec = new Region("Quebec");
    // Build the hierarchy
    earth->children = {na};
    na->children = {us, ca};
    us->children = {ny};
    ca->children = {caState};
    caState->children = {losAngeles, sanFrancisco};
    ca->children.push_back(ontario);
    ca->children.push_back(quebec);
    return earth; // Return the root node
}
//Function to perform Depth-First Search (DFS) and build parent mapping
void buildParentMapping(Region* node, unordered_map<string, string>& parent) {
    for (Region* child : node->children) {
        parent[child->name] = node->name; // Map child to its parent
        buildParentMapping(child, parent); // Recursively build for children
    }
}
//Function to find the smallest common region using parent mapping and ancestor tracing
string findSmallestCommonRegion(const unordered_map<string, string>& parent,
                                const string& region1, const string& region2) {
    // Step 1: Trace ancestors for region1
    unordered_set<string> ancestors1;
    string current = region1;
    while (parent.find(current) != parent.end()) {
        ancestors1.insert(current);
        current = parent.at(current);
    }
    ancestors1.insert(current); // Insert the root node
    // Step 2: Trace ancestors for region2 and find the smallest common ancestor
    current = region2;
    while (parent.find(current) != parent.end()) {
        if (ancestors1.find(current) != ancestors1.end()) {
            return current; // Found the smallest common ancestor
        }
        current = parent.at(current);
    }
    // If no common ancestor is found (should not ideally happen in a well-formed hierarchy)
    return "";
}
//Function to delete the hierarchical structure to prevent memory leaks
void deleteHierarchy(Region* node) {
    if (node == nullptr) return;
    for (Region* child : node->children) {
        deleteHierarchy(child);
    }
    delete node;
}
int main() {
    // Build the hierarchical structure
    Region* root = buildHierarchy();
    // Initialize parent mapping and build it using DFS
    unordered_map<string, string> parent;
    buildParentMapping(root, parent);
    // Example usage: Find smallest common region
    string region1 = "San Francisco";
    string region2 = "Quebec";
    string smallestCommonRegion = findSmallestCommonRegion(parent, region1, region2);
    if (!smallestCommonRegion.empty()) {
        cout << "Smallest Common Region: " << smallestCommonRegion << endl;
    } else {
        cout << "No common region found between " << region1 << " and " << region2 << endl;
    }
    // Clean up: Delete the hierarchical structure
    deleteHierarchy(root);
    return 0;
}

输出

 
Smallest Common Region: Canada

解释

该问题涉及一个分层结构，其中每个区域（节点）与其父区域相连，形成一个树状结构。给定该层级结构中的两个区域，目标是确定对两个区域都通用的最小区域，即它们的最近公共祖先。

C++ 实现采用结构化方法来查找分层结构中的最小公共区域。通过利用父节点映射和祖先追踪技术，该实现提供了一种高效且可扩展的解决方案，适用于需要分层数据分析和导航的各种现实世界应用。可以根据不同场景下的特定要求或额外功能进行调整，以确保处理复杂分层关系时的健壮性和适应性。

数据结构：Region

Region 结构封装了一个区域的名称 (string name) 及其子节点 (vector<Region*> children)。该结构对于表示区域之间的分层关系至关重要。每个区域可以有多个子节点，从而可以灵活且可扩展地表示该层级结构。

构建层级结构：buildHierarchy 函数

buildHierarchy 函数从根节点“Earth”开始初始化分层结构，并向下构建树。例如，“North America”成为“Earth”的子节点，“United States”和“Canada”成为“North America”的子节点。这种层级结构的构建递归地进行，定义了父子区域之间的关系。

构建父节点映射：buildParentMapping 函数

buildParentMapping 函数采用深度优先搜索 (DFS) 来遍历分层结构。在遍历过程中，它会填充一个 unordered_map<string, string> parent，其中每个区域都映射到其父区域。此映射对于稍后高效地追踪祖先和查找最小公共区域至关重要。

查找最小公共区域：findSmallestCommonRegion 函数

祖先追踪法

追踪 region1 的祖先

函数从 region1 开始，使用父节点映射向上追踪层级结构，直到到达根节点（“Earth”）。它将遇到的每个区域存储在 ancestors1 中。

追踪 region2 的祖先

类似地，函数从该区域向上追踪，并将祖先存储在 ancestors2 中。

识别最小公共祖先

通过迭代 ancestors1，函数将每个祖先与 ancestors2 进行比较，以找到第一个公共祖先。这个公共祖先是区域 1 和区域 2 在其祖先中共享的最小区域。

main 函数中的示例用法

初始化：main 函数使用 buildHierarchy 初始化分层结构，并使用 buildParentMapping 构建父节点映射。

查找最小公共区域：本教程演示了如何使用findSmallestCommonRegion来查找并打印两个指定区域（例如，“San Francisco”和“Quebec”）之间的最小公共区域。

内存管理：deleteHierarchy 函数

清理：为防止内存泄漏，deleteHierarchy 函数会递归删除从根节点开始所有动态分配的 Region 对象。这确保在使用分层结构后进行有效的内存管理。

复杂度分析

时间复杂度

构建层级结构（buildHierarchy 函数）

buildHierarchy 函数通过递归创建 Region 对象并建立父子关系来构建分层结构。构建该层级结构的时间复杂度为O(N)，其中 N 是层级结构中的总区域数。每个区域都会被访问一次以建立父子连接。

构建父节点映射（buildParentMapping 函数）

使用深度优先搜索 (DFS)，buildParentMapping 函数遍历分层结构以填充父节点映射（unordered_map<string, string>）。此操作的时间复杂度为 O(N)，与构建层级结构类似，因为每个区域都会被处理一次以建立父子关系。

祖先追踪（findSmallestCommonRegion 函数）

追踪给定区域的祖先包括使用父节点映射向上移动层级结构，直到到达根节点。此追踪操作每个节点的平均时间复杂度为O(log N)，因为它需要导航父关系链。因此，追踪两个区域（region1 和 region2）的祖先的总时间复杂度为 O(log N) + O(log N) = O(log N)，其中 N 是分层结构的深度。

比较祖先

在追踪完两个区域的祖先后，findSmallestCommonRegion函数会比较祖先集（ancestors1 和 ancestors2）以找到最小的公共区域。此比较的时间复杂度为 O(min(A, B))，其中 A 和 B 分别是为区域 1 和区域 2 追踪的祖先数量。在最坏情况下，当 A 和 B 相等时，结果为O(A) 或 O(B)。

使用此方法查找最小公共区域的总时间复杂度主要由构建层级结构和父节点映射的操作决定，即O(N)，其中 N 是区域数。

空间复杂度

层级结构和父节点映射

存储分层结构和父节点映射（parent map）的空间复杂度为O(N)，其中 N 是区域数。这包括存储 Region 对象和父节点映射（以 unordered_map<string, string> 格式）所需的内存。

祖先追踪

在追踪单个区域的祖先时，最坏情况下的空间复杂度为O(log N)，其中 log N 是从该区域到根节点的最大深度。这包括递归遍历期间调用堆栈的空间或迭代遍历期间循环堆栈的空间。

比较和结果存储

在祖先追踪过程中，还需要额外的空间来存储祖先集（ancestors1 和 ancestors2）。这些集合的空间复杂度为 O(A + B)，其中 A 和 B 分别是为区域 1 和区域 2追踪的祖先数量。

解决方案的总空间复杂度为O(N) + O(log N) + O(A + B)，其中 N 是区域数，A 和 B 分别是为区域 1 和区域 2 追踪的祖先数量。

方法二：迭代检查查找最小公共区域

在分层结构中查找两个节点之间的最小公共区域（或最近公共祖先）涉及追踪它们的祖先并识别它们共享的第一个公共祖先。

程序

 
#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;
//Function to find smallest common region (least common ancestor)
string findSmallestCommonRegion(const unordered_set<string>& ancestors1, 
                                const unordered_set<string>& ancestors2) {
    // Iterate through ancestors1 and find the first common ancestor in ancestors2
    for (const auto& ancestor : ancestors1) {
        if (ancestors2.count(ancestor) > 0) {
            return ancestor; // Found the smallest common ancestor
        }
    }
    return ""; // No common ancestor found (should not ideally happen in the well-formed hierarchy)
}
int main() {
    // Example usage
    unordered_set<string> ancestors1 = {"San Francisco", "California", "United States", "North America", "Earth"};
    unordered_set<string> ancestors2 = {"Quebec", "Canada", "North America", "Earth"};
    string smallestCommonRegion = findSmallestCommonRegion(ancestors1, ancestors2);
    if (!smallestCommonRegion.empty()) {
        cout << "Smallest Common Region: " << smallestCommonRegion << endl;
    } else {
        cout << "No common region found between given nodes." << endl;
    }
    return 0;
}

输出

 
Smallest Common Region: Earth

解释

该问题涉及导航一个分层结构，其中每个节点代表一个区域，并且除了根节点外，每个节点都有一个父节点。给定该层级结构中的两个节点，目标是识别对两个节点都通用的最小区域，即它们的最近公共祖先。

迭代检查方法提供了一种清晰有效的方法来查找分层结构中两个节点之间的最小公共区域。该方法确保了在确定分层数据表示（如地理区域、组织结构或家谱树）中的分层关系和共同祖先方面的效率和清晰度。可以根据涉及分层数据分析和管理的各种应用的特定要求或所需的优化进行调整。

追踪祖先并存储在集合中

祖先追踪从每个给定节点（节点 1 和节点 2）开始，并通过父引用向上移动，直到到达层级结构的根节点。

在遍历过程中，遇到的每个区域（节点的名称）都会存储在一个集合中（nodes1 的 ancestors1 和 nodes2 的 ancestors2）。此集合可确保每个祖先仅记录一次，避免重复。

比较集合以查找公共祖先

一旦 ancestors1 和 ancestors2 分别用节点 1 和节点 2 的祖先填充完毕，下一步就是找到最小的公共祖先。

公共祖先是从最低级别祖先（最接近节点）向上遇到的第一个存在于两个集合中的节点。

迭代检查过程

初始化：开始迭代祖先，从最低级别的祖先开始（例如，“San Francisco”和“Quebec”）。

比较迭代：将ancestors1中的每个祖先与 ancestors2 进行比较，反之亦然。

从每个集合中最后添加的祖先开始（因为集合是无序的，可以是任何元素，但通常是最后添加的）。

迭代比较元素，直到找到存在于两个集合中的第一个公共祖先。

终止

一旦找到并存在于两个集合（ancestors1 和 ancestors2）中的第一个公共祖先，它就被认为是节点 1 和节点 2 之间的最小公共区域。

要比较的节点

node1 = "San Francisco"

node2 = "Quebec"

祖先追踪

从 node1 和 node2 向上追踪祖先以填充 ancestors1 和 ancestors2。

示例集合

ancestors1 = {"San Francisco", "California", "United States", "North America", "Earth"}

ancestors2 = {"Quebec", "Canada", "North America", "Earth"}

迭代检查

从最低级别的祖先开始检查（例如，“San Francisco”和“Quebec”）。

迭代比较集合 ancestors1 和 ancestors2。识别出在两个集合中找到的第一个公共祖先：“North America”。

复杂度分析

时间复杂度主要取决于层级的高度 (log N) 和祖先集的大小 (min(A, B))，而空间复杂度取决于祖先和层级结构的存储。这些复杂度确保了该解决方案可扩展且高效，适用于涉及分层数据分析和管理的各种应用。

时间复杂度分析

祖先追踪

时间复杂度：追踪每个节点（node1 和 node2）的祖先包括通过父引用向上移动，直到到达层级结构的根节点。此操作对于每个节点的时间复杂度为O(H)，其中 H 是层级的高度。

假设层级结构是平衡的或接近平衡的，H 可以近似为 log N，其中 N 是层级结构中的区域数。

因此，追踪两个节点（node1 和 node2）的祖先的时间复杂度为O(log N)。

将祖先存储在集合中

时间复杂度：将祖先存储在集合（ancestors1 和 ancestors2）中涉及将每个祖先插入到集合中。插入到 unordered set 的平均时间复杂度为 O(1)。

因此，将 H 个祖先插入到每个集合（ancestors1 和 ancestors2）中的总时间复杂度为O(H)，对于两个集合而言。

迭代检查

时间复杂度：一旦 ancestors1 和 ancestors2 被填充，查找最小公共区域就涉及迭代较小的集合（O(min(A, B))，其中 A 和 B 分别是 ancestors1 和 ancestors2 的大小），并检查另一个集合中的公共元素。

在最坏情况下，当两个集合大小相等 (A = B)时，迭代检查的时间复杂度为O(A) 或 O(B)。

总体时间复杂度

将上述操作结合起来，总时间复杂度主要由祖先追踪 (O(log N)) 和迭代检查 (O(min(A, B))) 决定。

因此，总时间复杂度为O(log N + min(A, B))。

空间复杂度分析

祖先的存储

空间复杂度：每个节点的祖先都存储在集合中（ancestors1 和 ancestors2）。每个集合的空间复杂度为 O(H)，其中 H 是层级的高度。

在最坏情况下，当两个节点都处于最大深度时（H = log N），两个集合的总空间复杂度为O(log N)。

附加空间

空间复杂度：存储层级结构本身需要额外的空间（O(N)，用于存储 Region 对象和父节点引用）。

在递归或迭代操作期间的临时变量和函数调用堆栈也会占用空间，这在深度优先搜索操作中通常为 O(log N)。

总体空间复杂度

将上述所有组件结合起来，总空间复杂度主要由存储祖先的空间 (O(log N)) 和层级结构的空间 (O(N)) 决定。

因此，总空间复杂度为O(N + log N)。

下一主题C++17 功能和增强

C++ 中查找最小公共区域

引言

现实世界中的分层结构

地理区域

组织图

文件系统

生物分类

方法一：父节点映射和祖先追踪法

程序

解释

祖先追踪法

复杂度分析

空间复杂度

方法二：迭代检查查找最小公共区域

程序

解释

时间复杂度分析

空间复杂度分析

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中查找最小公共区域

引言

现实世界中的分层结构

地理区域

组织图

文件系统

生物分类

方法一：父节点映射和祖先追踪法

程序

解释

祖先追踪法

复杂度分析

空间复杂度

方法二：迭代检查查找最小公共区域

程序

解释

时间复杂度分析

空间复杂度分析

相关帖子

C++ 重建行程

C++ 中带有海洋景观的建筑

C++ 中计算第 n 个弗罗贝尼乌斯数