包含全局最小值的向量索引

Question

给定一个向量向量，是否有一种最佳方法来确定保持全局最小值的向量的索引？ Big-O 表示法的复杂性是多少？

#include <algorithm>
#include <iostream>
#include <vector>
unsigned getMinimumIndex(std::vector<std::vector<unsigned>> const& a) {
if (!a.size())
return 0;
unsigned ret = 0; unsigned temp; unsigned global = 1 << 31;
for (std::size_t idx = 0; idx < a.size(); ++idx) {
if ((temp = *std::min_element(std::begin(a[idx]), std::end(a[idx]))) < global) {
global = temp;
ret = idx;
}
}
return ret;
}
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-th vector posseses the value '0'
return 0;
}

Answer 1

由于您的向量和向量中的数字都没有排序，因此您必须检查每个数字是否为最小值。 因此，您可以得到O(n(的复杂度。

你可以像以前一样使用迭代器，也可以简单地使用 2 for 循环并使用 a[i][j] 访问向量(由于迭代器缺少开销，这应该稍微快一点(。

另外 - 由于您只有无符号的 int，因此您可以在找到 0 时立即中断。