最大的二维数组的列使用分而治之

Question

假设我们有一个二维数组

1 2 3 1 
5 6 4 0 
0 3 2 1 
1 2 1 0 

有一个全球性的方式如何使用鸿沟找到列中的最大数目，如果攻克技术的长度每行都不一样？

我指的是寻找需要这一步骤的二维数组内峰的一个步骤。

一维数组它会是这样的

int maxNumber(vector<int> a , int min , int max){ 
    if(min == max) 
     return a[min]; 
    int mid = (min + max)/2; 
    int i = maxNumber(a , min , mid); 
    int j = maxNumber(a , mid +1, max); 
    if(i > j) 
     return i; 
    return j; 
    } 

    vector<int> v = { 1 , 2 , 5 , 0 , 10 , 9}; 
    cout << maxNumber(a , 0 , a.size() -1); 

现在对于N×N的N×M个或矩阵，我们可以做

int maxNumberCollum(vector<vector<int>> a , int row_min , int row_max , int size){ 
    if (row_min == row_max){ 
     return a[row_min][size]; 
    } 

    int row = (row_min + row_max)/2; 
    int i = maxNumberCollum(a , row_min , row  , size); 
    int j = maxNumberCollum(a , row + 1 , row_max , size); 

    if(i > j) 
     return i; 
    return j; 
}; 

vector< vector<int> > a = { { 1 , 2 , 3 }, 
          { 5 , 0 , 1 }, 
          { 6 , 2 , 0 } 
          }; 
cout << maxNumberCollum(a , 0 , a.size() -1 , 2) 

与列，我们希望作为参数传递给找到最大。

但是，如果我们不知道矩阵（2d数组）是NxN/NxM还是行的长度对于每一行都不相同，那么如何将它实现为2d数组将如何实现？

Answer 1

由于每个矢量都有其自己的大小，因此可以使用该信息来查找每行中的最大数。

如果你有这样一行：

return maxNumber(a[row_min], 0, a[row_min].size() - 1) 

Answer 2

如果考虑不同大小的矢量的矢量，关键的一点是：

return a[row_min][size]; 

通过调用你的1D函数替换确保你不会尝试访问那些超出范围的人。

举个例子，考虑下面的代码：

#include <iostream> 
#include <vector> 
#include <limits> 

using std::cout; 
using std::vector; 

const int lowest_int = std::numeric_limits<int>::lowest(); 

int max_number_in_column(const vector<vector<int>> &a, 
          size_t row_min, size_t row_max, size_t col) 
{ 
    if (row_min == row_max) { 
     return col < a[row_min].size() ? a[row_min][col] : lowest_int; 
    } 

    int row = (row_min + row_max)/2; 
    int i = maxNumberColumn(a, row_min, row,  col); 
    int j = maxNumberColumn(a, row + 1, row_max, col); 

    return i > j ? i : j; 
}; 

int main() { 
    vector<vector<int>> a = { 
     { 1 , 2 , 3 }, 
     { 5 , 0 , 1, -8 }, 
     { 6 , 2 } 
    }; 

    size_t col = 3; 
    int max = max_number_in_column(a, 0, a.size() - 1, col); 

    if (max > lowest_int) 
     cout << "The greater element of column " << col << " is " << max <<'\n'; 
    else 
     cout << "Unable to find a maximum value in column " << col << '\n'; 

    return 0; 
} 

我真的不明白的是为什么你正在尝试做这个使用分而治之的技术，而这将是一个更容易共同循环：

int max_number_in_column(const vector<vector<int>> &a , size_t col) 
{ 
    int max = lowest_int; 
    for (auto const &row : a) { 
     if (col < row.size() && row[col] > max) max = row[col]; 
    } 
    return max; 
};