C++：在数量可变的嵌套vector中查找首个公共元素

给定一个包含n个vector的std::vector（n未知或可动态变化），需要找到所有子vector中均存在的首个元素——这里的“首个”指从左到右遍历过程中，第一个满足在所有子vector里都出现过的元素。

示例1 #

std::vector<std::vector<int>> vec = { { 5,  7, 11, 12, 17, 23, 27 },
                                      { 8, 10, 12, 15, 17, 23, 28 },
                                      { 1,  2,  5,  6, 12, 22, 23 },
                                      { 3,  7,  9, 12, 17, 23, 28 } };

答案为12，它是遍历过程中第一个在所有子vector里都存在的元素。

已知固定数量子vector可通过硬编码多层循环实现，但需要适配子vector数量未知或可变的通用方案，同时需满足以下补充规则：

• 子vector并非始终有序，示例仅为便于查看；
• 若多个元素同时满足条件，任选其一即可，例如：

std::vector<std::vector<int>> vec = { { 0, 1 },
                                      { 1, 0 } };

0或1均为可接受答案；

• 若不存在所有子vector共有的元素，返回错误码（如-9999）；
• 子vector内元素可重复，例如：

std::vector<std::vector<int>> vec = { { 1, 2, 3, 1 },
                                      { 2, 3, 4, 3 },
                                      { 1, 2, 1, 3 } };

2和3是仅有的公共元素，其中2是符合要求的答案。

解题思路 #

1. 边界处理：如果外层vector为空，直接返回错误码；如果只有一个子vector，返回其第一个元素（非空时）。
2. 高效查找准备：将除第一个子vector外的所有子vector转换为std::unordered_set，利用其O(1)的查找时间复杂度提升效率。
3. 遍历判断：按顺序遍历第一个子vector的每个元素，检查该元素是否存在于所有其他子vector对应的unordered_set中，第一个满足条件的元素即为答案。
4. 无公共元素处理：遍历完第一个子vector仍无符合条件的元素，返回错误码。

代码实现 #

#include <vector>
#include <unordered_set>

int findFirstCommonElement(const std::vector<std::vector<int>>& vec) {
    // 外层vector为空
    if (vec.empty()) {
        return -9999;
    }
    // 只有一个子vector，返回首个元素（子vector非空时）
    if (vec.size() == 1) {
        return vec[0].empty() ? -9999 : vec[0][0];
    }

    // 转换其余子vector为unordered_set，加速查找
    std::vector<std::unordered_set<int>> elementSets;
    elementSets.reserve(vec.size() - 1);
    for (size_t i = 1; i < vec.size(); ++i) {
        elementSets.emplace_back(vec[i].begin(), vec[i].end());
    }

    // 遍历第一个子vector，找第一个全局公共元素
    for (int num : vec[0]) {
        bool isCommon = true;
        for (const auto& set : elementSets) {
            if (set.find(num) == set.end()) {
                isCommon = false;
                break;
            }
        }
        if (isCommon) {
            return num;
        }
    }

    // 无公共元素
    return -9999;
}

代码说明 #

• unordered_set的使用大幅降低了元素存在性判断的时间成本，尤其适合子vector元素较多的场景。
• 遍历第一个子vector的元素，确保找到的是首个符合条件的元素，完全匹配题目要求。
• 覆盖了所有边界场景：外层vector为空、子vector为空、仅单个子vector的情况。
• 子vector内的重复元素不影响结果，因为unordered_set会自动去重，只要元素存在至少一次就会被识别。

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