如何确定含全局最小值的二维vector子vector索引？时间复杂度是多少？

最优方法与时间复杂度 #

要确定包含全局最小值的子vector索引，不存在比遍历所有元素更快的方法——因为全局最小值可能藏在任意子vector的任意位置，你必须检查每一个元素才能确保不会漏掉它。

对应的最优时间复杂度是 O(N)，其中N是二维vector的总元素数量。这个复杂度是理论下界：任何算法都无法在少于O(N)的时间内完成任务，毕竟只要遗漏一个元素，就有可能刚好错过全局最小值。

代码分析与优化说明 #

你提供的代码逻辑是正确的，已经实现了这个最优复杂度的解法：遍历每个子vector，用std::min_element找到当前子vector的最小值，再对比更新全局最小值对应的索引。

不过可以做一些小优化，让代码更健壮、易读：

1. 初始化全局最小值时，改用第一个子vector的最小值，避免固定初始值1 << 31可能带来的范围错误（比如子vector元素都是大于该值的无符号数时，初始判断会失效）
2. 用更简洁的变量命名和范围逻辑提升可读性

优化后的代码示例：

#include <algorithm>
#include <iostream>
#include <vector>

unsigned getMinimumIndex(const std::vector<std::vector<unsigned>>& a) {
    if (a.empty()) return 0; // 空输入的边界处理
    
    unsigned target_idx = 0;
    unsigned global_min = *std::min_element(a[0].begin(), a[0].end());
    
    for (size_t idx = 1; idx < a.size(); ++idx) {
        const auto current_sub_min = *std::min_element(a[idx].begin(), a[idx].end());
        if (current_sub_min < global_min) {
            global_min = current_sub_min;
            target_idx = idx;
        }
    }
    return target_idx;
}

int main() {
    std::vector<std::vector<unsigned>> a = {{2, 4, 6, 8}, {3, 9, 5, 7}, {3, 4, 4, 3}, {2, 8, 3, 2}, {4, 4, 4, 0}, {1, 2, 3, 4}};
    std::cout << getMinimumIndex(a); // 输出4，对应包含0的子vector
    return 0;
}

额外细节说明 #

• 如果有多个子vector包含相同的全局最小值，上述代码会返回第一个出现的子vector索引。如果需要返回最后一个或所有符合条件的索引，可以调整逻辑（比如遍历到最后才更新，或者收集所有符合条件的索引列表）
• 空输入的处理可以根据需求修改，比如抛出异常、返回std::numeric_limits<unsigned>::max()等特殊值

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