Максимум в столбце 2d массива с использованием разделяй и властвуй
Давайте предположим, что у нас есть 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 или длина строки не одинакова для каждой строки?
Решение
Поскольку каждый вектор имеет свой собственный размер, вы можете использовать эту информацию, чтобы найти максимальное число в каждой строке.
Где у вас есть эта строка:
return a[row_min][size];
замените его вызовом 1d-функции:
return maxNumber(a[row_min], 0, a[row_min].size() - 1)
Другие решения
Если вы рассматриваете вектор векторов разных размеров, ключевым моментом является обеспечение того, чтобы вы не пытались получить доступ к ним вне их границ.
В качестве примера рассмотрим следующий код:
#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;
};
detector