Преобразовать заданную верхнюю треугольную матрицу в одномерный массив

Опубликовано: 1 Декабря, 2021

Для данной верхнетреугольной матрицы M [] [] размерности N * N задача состоит в том, чтобы преобразовать ее в одномерный массив, хранящий только ненулевые элементы из матрицы.

Примеры:

Input: M[][] = {{1, 2, 3, 4}, {0, 5, 6, 7}, {0, 0, 8, 9}, {0, 0, 0, 10}}
Output: Row-wise: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Column-wise: {1, 2, 5, 3, 6, 8, 4, 7, 9, 10}
Explanation: All the non-zero elements of the matrix are {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Input: M[][] = {{1, 2, 3, }, {0, 4, 5}, {0, 0, 6}}
Output: Row-wise: {1, 2, 3, 4, 5, 6}
Column-wise: {1, 2, 4, 3, 5, 6}
Explanation: All the non-zero elements of the matrix are {1, 2, 3, 4, 5, 6}

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: чтобы преобразовать заданную двумерную матрицу в одномерный массив, используются следующие два метода:

Строка - Главный порядок:

В этом методе элементы хранятся таким образом, что последовательные элементы строки последовательно помещаются в массив.

РЯДНЫЙ ЗАКАЗ

Следующая формула используется для нахождения правильного положения ненулевых элементов матрицы в массиве:

Element present at index (i, j) in the matrix is placed at [N * (i – 1) – (i – 2) * (i -1) /2] + (j – i)
where 1 ≤ i, j ≤ N and i ≤ j

Столбец-майор Порядок:

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

КОЛОННА-ГЛАВНЫЙ ЗАКАЗ

Следующая формула используется для определения правильного положения ненулевых элементов матрицы:

Element present at index (i, j) in the matrix is placed at [j * (j – 1) / 2] + i – 1
where 1 ≤ i, j ≤ N and i ≤ j.

Выполните следующие действия, чтобы решить проблему:

Инициализируйте массив A [] для хранения ненулевых матричных элементов.
Пройдите по матрице M [] [] .
Найдите правильные индексы ненулевых матричных элементов в массиве A [], используя приведенные выше формулы.
Поместите ненулевые элементы в правильные индексы A [] соответственно.
Наконец, выведите полученный массив A [] .

Ниже представлена реализация описанного выше подхода:

C ++

 // C++ Program to convert a given
 // upper triangular matrix to 1D array
 #include <iostream>
 using namespace std;
 // Create a class of Upper
 // Triangular Matrix
 class UTMatrix {
 private :
    // Size of Matrix
    int n; 
    // Pointer
    int * A; 
    // Stores count of
    // non-zero elements
    int tot;
 public :
    // Constructor
    UTMatrix( int N)
    {
        this ->n = N;
        tot = N * (N + 1) / 2;
        A = new int [N * (N + 1) / 2];
    }
    // Destructor
    ~UTMatrix() { delete [] A; } 
    // Function to display array
    void Display( bool row = true ); 
    // Function to generate array in
    // Row - Major order
    void setRowMajor( int i, int j, int x); 
    // Function to generate array in
    // Column - Major order
    void setColMajor( int i, int j, int x); 
    // Function to return size of array
    int getN() { return n; }
 };
 // Function to generate array from given matrix
 // by storing elements in column major order
 void UTMatrix::setColMajor( int i, int j, int x)
 {
    if (i <= j) {
        int index = ((j * (j - 1)) / 2) + i - 1;
        A[index] = x;
    }
 }
 // Function to generate array from given matrix
 // by storing elements in row major order
 void UTMatrix::setRowMajor( int i, int j, int x)
 {
    if (i <= j) {
        int index
            = (n * (i - 1) - (((i - 2) * (i - 1)) / 2))
              + (j - i);
        A[index] = x;
    }
 }
 // Function to display array elements
 void UTMatrix::Display( row) bool
 {
    for ( int i = 0; i < tot; i++) {
        cout << A[i] << " " ;
    }
    cout << endl;
 }
 // Function to generate and
 // display array in Row-Major Order
 void displayRowMajor( int N)
 {
    UTMatrix rm(N);
    // Generate array in
    // row-major form
    rm.setRowMajor(1, 1, 1);
    rm.setRowMajor(1, 2, 2);
    rm.setRowMajor(1, 3, 3);
    rm.setRowMajor(1, 4, 4);
    rm.setRowMajor(2, 2, 5);
    rm.setRowMajor(2, 3, 6);
    rm.setRowMajor(2, 4, 7);
    rm.setRowMajor(3, 3, 8);
    rm.setRowMajor(3, 4, 9);
    rm.setRowMajor(4, 4, 10);
    // Display array elements in
    // row-major order
    cout << "Row-Wise: " ; 
    rm.Display();
 }
 // Function to generate and display
 // array in Column-Major Order
 void displayColMajor( int N)
 {
    UTMatrix cm(N);
    // Generate array in
    // column-major form
    cm.setColMajor(1, 1, 1);
    cm.setColMajor(1, 2, 2);
    cm.setColMajor(1, 3, 3);
    cm.setColMajor(1, 4, 4);
    cm.setColMajor(2, 2, 5);
    cm.setColMajor(2, 3, 6);
    cm.setColMajor(2, 4, 7);
    cm.setColMajor(3, 3, 8);
    cm.setColMajor(3, 4, 9);
    cm.setColMajor(4, 4, 10);
    // Display array elements in
    // column-major form
    cout << "Column-wise: " ;
    cm.Display( false );
 }
 // Driver Code
 int main()
 {
    // Size of row or column
    // of square matrix
    int N = 4; 
    displayRowMajor(N);
    displayColMajor(N);
    return 0;
 }

Ява

 // Java program to convert a given
 // upper triangular matrix to 1D array
 // Create a class of Upper
 // Triangular Matrix
 class UTMatrix{
    
// Size of Matrix
 private int n;
 private int [] A = new int [n];
 // Stores count of
 // non-zero elements
 private int tot;
 // Constructor
 public UTMatrix( int N)
 {
    this .n = N;
    tot = N * (N + 1 ) / 2 ;
    A = new int [N * (N + 1 ) / 2 ];
 }
 // Function to display array
 void Display( boolean row)
 {
    for ( int i = 0 ; i < tot; i++)
    {
        System.out.print(A[i] + " " );
    }
    System.out.println();
 }
 // Function to generate array in
 // Row - Major order
 void setRowMajor( int i, int j, int x)
 {
    if (i <= j)
    {
        int index = (n * (i - 1 ) - (((i - 2 ) *
                         (i - 1 )) / 2 )) + (j - i);
        A[index] = x;
    }
 }
 // Function to generate array in
 // Column - Major order
 void setColMajor( int i, int j, int x)
 {
    if (i <= j) {
        int index = ((j * (j - 1 )) / 2 ) + i - 1 ;
        A[index] = x;
    }
 }
 // Function to return size of array
 int getN()
 {
    return n;
 }
 }
 class GFG{
 // Function to generate and
 // display array in Row-Major Order
 static void displayRowMajor( int N)
 {
    UTMatrix rm = new UTMatrix(N); 
    // Generate array in
    // row-major form
    rm.setRowMajor( 1 , 1 , 1 );
    rm.setRowMajor( 1 , 2 , 2 );
    rm.setRowMajor( 1 , 3 , 3 );
    rm.setRowMajor( 1 , 4 , 4 );
    rm.setRowMajor( 2 , 2 , 5 );
    rm.setRowMajor( 2 , 3 , 6 );
    rm.setRowMajor( 2 , 4 , 7 );
    rm.setRowMajor( 3 , 3 , 8 );
    rm.setRowMajor( 3 , 4 , 9 );
    rm.setRowMajor( 4 , 4 , 10 ); 
    // Display array elements in
    // row-major order
    System.out.print( "Row-Wise: " ); 
    rm.Display( false );
 }
 // Function to generate and display
 // array in Column-Major Order
 static void displayColMajor( int N)
 {
    UTMatrix cm = new UTMatrix(N); 
    // Generate array in
    // column-major form
    cm.setColMajor( 1 , 1 , 1 );
    cm.setColMajor( 1 , 2 , 2 );
    cm.setColMajor( 1 , 3 , 3 );
    cm.setColMajor( 1 , 4 , 4 );
    cm.setColMajor( 2 , 2 , 5 );
    cm.setColMajor( 2 , 3 , 6 );
    cm.setColMajor( 2 , 4 , 7 );
    cm.setColMajor( 3 , 3 , 8 );
    cm.setColMajor( 3 , 4 , 9 );
    cm.setColMajor( 4 , 4 , 10 ); 
    // Display array elements in
    // column-major form
    System.out.print( "Column-wise: " );
    cm.Display( false );
 }
 // Driver Code
 public static void main(String[] args)
 {
    
    // Size of row or column
    // of square matrix
    int N = 4 ; 
    displayRowMajor(N);
    displayColMajor(N);
 }
 }
 // This code is contributed by dharanendralv23

Выход:

 По строкам: 1 2 3 4 5 6 7 8 9 10 
По столбцам: 1 2 5 3 6 8 4 7 9 10

Сложность времени: O (N * N)
Вспомогательное пространство: O (N * N)

Вниманию читателя! Не прекращайте учиться сейчас. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Technical Scripter Школьное программирование

Преобразовать заданную верхнюю треугольную матрицу в одномерный массив

C ++

Ява

РЕКОМЕНДУЕМЫЕ СТАТЬИ