Maximum в колонке 2d массива, используя разделяй и властвуй

Question

Давайте предположим, что мы имеем 2d массив

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

Есть глобальный способ, как найти максимальное число в колонке, используя разделяй и властвуй технику, если длина из строка не была одинаковой для каждой строки?

Я имею в виду шаг в поиске пика внутри массива 2d, который требует этого шага.

На 1d массиве было бы что-то вроде

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); 

Теперь для NxN или матрицы NXM мы могли бы сделать

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-массива, учитывая тот факт, что мы не знаем, является ли матрица (2d-массив) NxN/NxM или длина строки не одинакова для каждой строки?

Answer 1

Поскольку каждый вектор имеет свой собственный размер, вы можете использовать эту информацию, чтобы найти максимальное число в каждой строке.

Где у вас есть эта строка:

return a[row_min][size]; 

заменить его призыв к вашей 1d функции:

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

Answer 2

Если рассматривать вектор векторов разных размеров, ключевым моментом является убедитесь, что вы не пытаетесь получить доступ к ним из своих границ.

В качестве примера, рассмотрим следующий код:

#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; 
};