在C++中找到二维数组的极值点的最佳方法是什么？

Question

我正在寻找一种方法来查找C++中二维整数数组的最大值和最小值。我知道std::max_element()和std::min_element()，但它们似乎只适用于一维数组。

可以通过以下方式声明和初始化2D数组：

int temp[5][5];

for(int x = 0; x < 5; x++)
{
    for(int y = 0; y < 5; y++)
    {
        temp[x][y] = some_random_number;
    }
}

一个简单的方法是像这样做：

int min = high_number;
int max = low_number;

for(int x = 0; x < 5; x++)
{
    for(int y = 0; y < 5; y++)
    {
        if(temp[x][y] < min)
        {
            min = temp[x][y];
        }
        if(temp[x][y] > max)
        {
            max = temp[x][y];
        }
    }
}

但这似乎并不是很优化。有人能给一些建议或提出更好的想法吗？

- TomBombadil

---

不要优化，做一个简单而愚蠢的实现，易于调试。当出现瓶颈时进行优化，通过分析性能来确定。 - Ryp

没有更好的解决方案（也许有一些糖可以节省一些打字） - user2249683

你能优化查找最小/最大值的唯一方法是按行或列对数组进行排序。这会增加插入/填充数组的复杂性，但你可以在O(n)的时间内找到最小/最大值，其中n是行数或列数。 - mstbaum

@DieterLücking：std::minmax_element的复杂度比std::min_element+std::max_element低。分别为3/2和2。 - Jarod42

Answer 1

您仍然可以像这样使用std::min_element和std::max_element：

int arr[2][2] = {{434, 43}, {9826, 2}};
auto pair = std::minmax_element(&arr[0][0], &arr[0][0] + 4);

演示

这里的 4 是元素总数。

请注意，为了可读性，上述解决方案使用了 operator& 来获取数组开头的地址，但建议使用 std::addressof，因为 operator& 可能会被重载。

如果需要，您还可以声明辅助函数来获得等效的二维数组 begin 和 end 函数：

template<typename T, std::size_t N, std::size_t M>
auto bi_begin(T (&arr)[N][M]) {
    return std::addressof(arr[0][0]);
}

template<typename T, std::size_t N, std::size_t M>
auto bi_end(T (&arr)[N][M]) {
    return bi_begin(arr) + N * M;
}

演示

出于避免在此引发无穷无尽的讨论，我有意避免使用“begin”和“end”这两个名称。

---

总体而言，我建议定义一个“matrix”类型，其实现为具有M * N个元素的“std::array”，然后提供适当的“begin”和“end”成员函数，可以与任何标准算法一起使用。

- Shoe

---

你甚至可以使用std::minmax_elementгЂ‚ - Jarod42

值得一提的是，我认为 - 这适用于数组的数组，就像这里和问题中所示的那样。但不适用于类似作用的指向数组的指针的数组。 - Drew Dormann

@Jarod42 感谢您的建议。 - Shoe

Answer 2

如果对于数组/矩阵的内容没有其他限制，你不能比查看每个元素更好。这意味着你的解决方案实际上是在渐进运行时间方面的最优解。

我还会认为从可读性的角度来看，这也是不错的，但有些人可能会觉得以下方式更容易阅读（因为它更短）：

for(int x = 0; x < 5; x++)
{
   for(int y = 0; y < 5; y++)
   {
      min = std::min(temp[x][y], min);
      max = std::max(temp[x][y], max);
   }
}

- Tilo

Answer 3

如果你改变数组的类型为

constexpr int n = 5;
constexpr int m = 7;
std::array<int,n*m> ar;

并且像访问一样

ar[i*n + j]

那么你只需要写

auto min = std::min_element(ar.begin(), ar.end());
auto max = std::max_element(ar.begin(), ar.end());

- Spyros

---

你甚至可以使用 std::minmax_element。 - Jarod42

Answer 4

仅通过更改您的结构，您可能可以使用迭代器

int main()
{
    int c_array[5] = {};
    std::array<int, 5> cpp_array = {};
    std::vector<int> cpp_dynarray(5);

    auto c_array_begin = std::begin(c_array); // = c_array + 0
    auto c_array_end = std::end(c_array);     // = c_array + 5

    auto cpp_array_begin = std::begin(cpp_array); // = cpp_array.begin()
    auto cpp_array_end = std::end(cpp_array);     // = cpp_array.end()

    auto cpp_dynarray_begin = std::begin(cpp_dynarray); // = cpp_dynarray.begin()
    auto cpp_dynarray_end = std::end(cpp_dynarray);     // = cpp_dynarray.end()
}

并使用循环，例如：

mypointer = arr;
for(auto it = arr.begin(); it != arr.end(); ++it) {
        min = std::min(*mypointer, min)
        max = std::max(*mypointer, max)
}

- Vuwox