Démonstration animée du stockage compressé d'une matrice triangulaire

给定一个维度为 N * N的 下三角矩阵 M[][] ，任务是通过仅存储非零元素将其转换为一维数组。

例子：

输入： M[][] = {{1, 0, 0, 0}, {2, 3, 0, 0}, {4, 5, 6, 0}, {7, 8, 9, 10}}
输出：
按行：{1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 按
列：{1, 2, 4, 7, 3, 5, 8, 6, 9, 10解释
：矩阵的所有非零元素为{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}。
将这些元素按行方式排列在一维数组中会生成序列 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}。
将这些元素按列排列在一维数组中会生成序列 {1, 2, 4, 7, 3, 5, 8, 6, 9, 10}。

输入： M[][] = {{1, 0, 0, }, {2, 3, 0}, {4, 5, 6}} 输出：按行：{1, 2, 3, 4
,
5 , 6}
按列：{1, 2, 4, 3, 5, 6}

方法： 要将二维矩阵转换为一维数组，可以使用以下两种方法：

行 – 主要订单 ：

在此方法中，行的相邻元素在数组中彼此相邻放置。

下面的公式用于找出下三角矩阵的非零元素在一维数组中各自的位置。

位置 (i, j) 处矩阵元素的索引= ((i * (i – 1))/2 + j – 1)
其中 1 ? 我，j？尼和我？ j

专栏 – 主要订单 ：

在此方法中，列的连续元素在数组中相邻放置。

下面的公式用于找出下三角矩阵的非零元素在一维数组中各自的位置。

位置(i, j) 处的矩阵元素索引 = (N * (j – 1) – ((j – 2) * (j – 1))/2) + (i – j)
其中 1 ？我，j？尼和我？ j .

请按照以下步骤解决问题：

初始化一个数组（例如 A[] ） 来存储矩阵的非零元素。
遍历矩阵 M[][] 并使用行优先映射公式找到矩阵的非零元素在数组 A[] 中的索引，并将每个非零元素插入数组 A[] 中。
完成上述步骤后，打印数组 A[] 进行行优先映射。
再次遍历矩阵 M[][] 并使用列主映射公式找到矩阵的非零元素在数组 A[] 中的索引，并将每个非零元素插入数组 A[] 中。
完成上述步骤后，打印数组 A[] 以进行列主映射。

下面是上述方法的实现：

C++
Java
Python3
C＃
JavaScript

C++

              
                
                    // C++ program for the above approach
#include <iostream>
using namespace std;
 
// Class of Lower Triangular Matrix
class LTMatrix {
 
private:
    // Size of Matrix
    int
                          n;
 
    // Pointer
    int* A;
 
    // Stores the count of non-zero
    // elements
    int
                          tot;
 
public:
    // Constructor
    LTMatrix(int N)
    {
        this->n = N;
        tot = N * (N + 1) / 2;
        A = new int[N * (N + 1) / 2];
    }
 
    // Destructor
    ~LTMatrix() { 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 find size of array
    int
                          getN() { return n; }
};
 
// Function to generate array from
// given matrix by storing elements
// in column major order
                        
void LTMatrix::setColMajor(int i, int j, int x)
                        
{
    if
                          (i >= j) {
 
        int index
            = (n * (j - 1) - (((j - 2) * (j - 1)) / 2))
              + (i - j);
 
        A[index] = x;
    }
}
 
// Function to generate array from
// given matrix by storing elements
// in row major order
                        
void LTMatrix::setRowMajor(int i, int j, int x)
                        
{
    if
                          (i >= j) {
        int index = (i * (i - 1)) / 2 + j - 1;
                        
        A[index] = x;
    }
}
 
// Function to display array elements
void LTMatrix::Display(bool row)
{
    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)
{
    LTMatrix rm(N);
 
    // Generate the array in the
    // row-major form
    rm.setRowMajor(1, 1, 1);
    rm.setRowMajor(2, 1, 2);
    rm.setRowMajor(2, 2, 3);
    rm.setRowMajor(3, 1, 4);
    rm.setRowMajor(3, 2, 5);
    rm.setRowMajor(3, 3, 6);
    rm.setRowMajor(4, 1, 7);
    rm.setRowMajor(4, 2, 8);
    rm.setRowMajor(4, 3, 9);
    rm.setRowMajor(4, 4, 10);
 
    // Display array elements
    // in row-major order
    cout << "Row-Wise:\n";
 
    rm.Display();
}
 
// Function to generate and display
// array in Column-Major Order
void displayColMajor(int N)
{
    LTMatrix cm(N);
 
    // Generate array in
    // column-major form
    cm.setColMajor(1, 1, 1);
    cm.setColMajor(2, 1, 2);
    cm.setColMajor(2, 2, 3);
    cm.setColMajor(3, 1, 4);
    cm.setColMajor(3, 2, 5);
    cm.setColMajor(3, 3, 6);
    cm.setColMajor(4, 1, 7);
    cm.setColMajor(4, 2, 8);
    cm.setColMajor(4, 3, 9);
    cm.setColMajor(4, 4, 10);
 
    // Display array elements
    // in column-major form
    cout << "Column-Wise:\n";
    cm.Display(false);
}
 
// Driver Code
int main()
{
    // Size of row or column
    // of square matrix
    int
                          N = 4;
 
    // Function Call for row major
    // mapping
    displayRowMajor(N);
 
    // Function Call for column
    // major mapping
    displayColMajor(N);
 
    return 0;
}

                  

              
            

Java

              
                
                    // Java program for the above approach
import java.io.*;
class GFG {
 
    // Class of Lower Triangular Matrix
    static
                          class LTMatrix {
 
        // Size of Matrix
        static int n;
                        
 
        // Pointer
        static int A[];
 
        // Stores the count of non-zero
        // elements
        static int tot;
 
        // Constructor
        LTMatrix(int N)
                        
        {
            this.n = N;
            tot = N * (N + 1) / 2;
            A = new int[N * (N + 1) / 2];
        }
 
        // Function to display array elements
        static void Display(boolean row)
        {
            for (int
                          i = 0; i < tot; i++) {
                System.out.print(A[i] + " ");
            }
            System.out.println();
        }
 
        // Function to generate array from
        // given matrix by storing elements
        // in row major order
        static void setRowMajor(int i, int j, int x)
        {
            if (i >= j) {
                int index = (i * (i - 1)) / 2 + j - 1;
                A[index] = x;
            }
        }
 
        // Function to generate array from
        // given matrix by storing elements
        // in column major order
        static void setColMajor(int i, int j, int x)
        {
            if (i >= j) {
 
                int index = (n * (j - 1)
                             - (((j - 2) * (j - 1)) / 2))
                            + (i - j);
                A[index] = x;
            }
        }
 
        // Function to find size of array
        static int getN() { return n; }
    }
 
    // Function to generate and display
    // array in Row-Major Order
    static
                          void displayRowMajor(int N)
    {
        LTMatrix rm = new LTMatrix(N);
 
        // Generate the array in the
        // row-major form
        rm.setRowMajor(1, 1, 1);
        rm.setRowMajor(2, 1, 2);
        rm.setRowMajor(2, 2, 3);
        rm.setRowMajor(3, 1, 4);
        rm.setRowMajor(3, 2, 5);
        rm.setRowMajor(3, 3, 6);
        rm.setRowMajor(4, 1, 7);
        rm.setRowMajor(4, 2, 8);
        rm.setRowMajor(4, 3, 9);
        rm.setRowMajor(4, 4, 10);
 
        // Display array elements
        // in row-major order
        System.out.println("Row-Wise:");
        rm.Display(false);
    }
 
    // Function to generate and display
    // array in Column-Major Order
    static
                          void displayColMajor(int N)
    {
        LTMatrix cm = new LTMatrix(N);
 
        // Generate array in
        // column-major form
        cm.setColMajor(1, 1, 1);
        cm.setColMajor(2, 1, 2);
        cm.setColMajor(2, 2, 3);
        cm.setColMajor(3, 1, 4);
        cm.setColMajor(3, 2, 5);
        cm.setColMajor(3, 3, 6);
        cm.setColMajor(4, 1, 7);
        cm.setColMajor(4, 2, 8);
        cm.setColMajor(4, 3, 9);
        cm.setColMajor(4, 4, 10);
 
        // Display array elements
        // in column-major form
        System.out.println("Column-Wise:");
        cm.Display(false);
    }
 
    // Driver Code
    public
                          static void main(String[] args)
    {
 
        // Size of row or column
        // of square matrix
        int N = 4;
 
        // Function Call for row major
        // mapping
        displayRowMajor(N);
 
        // Function Call for column
        // major mapping
        displayColMajor(N);
    }
}
 
// This code is contributed by Dharanendra L V.

                  

              
            

Python3

              
                
                    # Python3 program for the above approach
 
# Class of Lower Triangular Matrix
class LTMatrix:
     
    # Constructor
    def
                          __init__(self, N):
     
        self.n = N;
        self.tot =
                          N * (N + 1) // 2;
        self.A = [None] * (int(N * (N + 1) / 2));
     
    # Function to display array elements
    def
                          Display(self, row):
        for i in
                          range(int(self.tot)):
            print(self.A[i], end = " ")
        print()
 
    # Function to generate array from
    # given matrix by storing elements
    # in row major order
    def
                          setRowMajor(self, i, j, x):
     
        if (i >=
                          j):
            index = (i * (i - 1)) // 2 + j - 1;
            self.A[index] = x;
         
    # Function to generate array from
    # given matrix by storing elements
    # in column major order
    def
                          setColMajor(self, i, j, x):
     
        if (i >=
                          j) :
 
            index =int((self.n * (j - 1)
                              - (((j -
                          2) * (j - 1)) / 2))
                             + (i - j));
            self.A[index] = x;
         
    # Function to find size of array
    def
                          getN(self):
                        
        return self.n; 
 
# Function to generate and display
# array in Row-Major Order
                        
def displayRowMajor(N):
 
    rm = LTMatrix(N);
 
    # Generate the array in the
    # row-major form
    rm.setRowMajor(1, 1, 1);
    rm.setRowMajor(2, 1, 2);
    rm.setRowMajor(2, 2, 3);
    rm.setRowMajor(3, 1, 4);
    rm.setRowMajor(3, 2, 5);
    rm.setRowMajor(3, 3, 6);
    rm.setRowMajor(4, 1, 7);
    rm.setRowMajor(4, 2, 8);
    rm.setRowMajor(4, 3, 9);
    rm.setRowMajor(4, 4, 10);
 
    # Display array elements
    # in row-major order
    print("Row-Wise:");
    rm.Display(False);
 
# Function to generate and display
# array in Column-Major Order
def displayColMajor(N):
 
    cm = LTMatrix(N);
 
    # Generate array in
    # column-major form
    cm.setColMajor(1, 1, 1);
    cm.setColMajor(2, 1, 2);
    cm.setColMajor(2, 2, 3);
    cm.setColMajor(3, 1, 4);
    cm.setColMajor(3, 2, 5);
    cm.setColMajor(3, 3, 6);
    cm.setColMajor(4, 1, 7);
    cm.setColMajor(4, 2, 8);
    cm.setColMajor(4, 3, 9);
    cm.setColMajor(4, 4, 10);
 
    # Display array elements
    # in column-major form
    print("Column-Wise:");
    cm.Display(False);
 
 
# Driver Code
 
# Size of row or column
                        
# of square matrix
N = 4;
 
# Function Call for row major
# mapping
displayRowMajor(N);
 
# Function Call for column
# major mapping
displayColMajor(N);
 
# This code is contributed by phasing17

                  

              
            

C#

              
                
                    // C# program for the above approach
using System;
 
public class LTMatrix {
 
    // Size of Matrix
    static
                          int n;
 
    // Pointer
    static
                          int[] A;
 
    // Stores the count of non-zero
    // elements
    static
                          int tot;
 
    // Constructor
    public
                          LTMatrix(int N)
    {
        n = N;
        tot = N * (N + 1) / 2;
        A = new int[N * (N + 1) / 2];
    }
 
    // Function to display array elements
    public
                          void Display(Boolean row)
    {
        for (int
                          i = 0; i < tot; i++) {
            Console.Write(A[i] + " ");
        }
        Console.Write("");
    }
 
    // Function to generate array from
    // given matrix by storing elements
    // in row major order
    public
                          void setRowMajor(int i, int
                          j, int x)
                        
    {
        if (i >= j) {
            int index = (i * (i - 1)) / 2 + j - 1;
                        
            A[index] = x;
        }
    }
 
    // Function to generate array from
    // given matrix by storing elements
    // in column major order
    public
                          void setColMajor(int i, int
                          j, int x)
                        
    {
        if (i >= j) {
 
            int index
                = (n * (j - 1) - (((j - 2) * (j - 1)) / 2))
                  + (i - j);
            A[index] = x;
        }
    }
 
    // Function to find size of array
    static
                          int getN() { return n; }
}
class GFG {
 
    // Class of Lower Triangular Matrix
 
    // Function to generate and display
    // array in Row-Major Order
    static
                          void displayRowMajor(int N)
    {
        LTMatrix rm = new LTMatrix(N);
 
        // Generate the array in the
        // row-major form
        rm.setRowMajor(1, 1, 1);
        rm.setRowMajor(2, 1, 2);
        rm.setRowMajor(2, 2, 3);
        rm.setRowMajor(3, 1, 4);
        rm.setRowMajor(3, 2, 5);
        rm.setRowMajor(3, 3, 6);
        rm.setRowMajor(4, 1, 7);
        rm.setRowMajor(4, 2, 8);
        rm.setRowMajor(4, 3, 9);
        rm.setRowMajor(4, 4, 10);
 
        // Display array elements
        // in row-major order
        Console.WriteLine("Row-Wise:");
        rm.Display(false);
    }
 
    // Function to generate and display
    // array in Column-Major Order
    static
                          void displayColMajor(int N)
    {
        LTMatrix cm = new LTMatrix(N);
 
        // Generate array in
        // column-major form
        cm.setColMajor(1, 1, 1);
        cm.setColMajor(2, 1, 2);
        cm.setColMajor(2, 2, 3);
        cm.setColMajor(3, 1, 4);
        cm.setColMajor(3, 2, 5);
        cm.setColMajor(3, 3, 6);
        cm.setColMajor(4, 1, 7);
        cm.setColMajor(4, 2, 8);
        cm.setColMajor(4, 3, 9);
        cm.setColMajor(4, 4, 10);
 
        // Display array elements
        // in column-major form
        Console.WriteLine("\nColumn-Wise:");
        cm.Display(false);
    }
 
    // Driver Code
    public
                          static void Main()
    {
 
        // Size of row or column
        // of square matrix
        int N = 4;
 
        // Function Call for row major
        // mapping
        displayRowMajor(N);
 
        // Function Call for column
        // major mapping
        displayColMajor(N);
    }
}
 
// This code is contributed by Saurabh Jaiswal

                  

              
            

Javascript

              
                
                    // JS program for the above approach
 
// Class of Lower Triangular Matrix
class LTMatrix {
    // Constructor
    constructor(N)
    {
        this.n = N;
        this.tot = N * (N + 1) / 2;
        this.A = new
                          Array(Math.floor(N * (N + 1) / 2));
    }
 
    // Function to display array elements
    Display(row)
    {
        for (var
                          i = 0; i < this.tot; i++) {
            process.stdout.write(this.A[i] + " ");
                        
        }
        console.log();
    }
 
    // Function to generate array from
    // given matrix by storing elements
    // in row major order
    setRowMajor(i, j, x)
    {
        if (i >= j) {
            let index = (i * (i - 1)) / 2 + j - 1;
            this.A[index] = x;
        }
    }
 
    // Function to generate array from
    // given matrix by storing elements
    // in column major order
    setColMajor(i, j, x)
    {
        if (i >= j) {
 
            var index
                = Math.floor((this.n * (j - 1)
                              - (((j - 2) * (j - 1)) / 2))
                             + (i - j));
            this.A[index] = x;
        }
    }
 
    // Function to find size of array
    getN() { return this.n; }
}
 
// Function to generate and display
// array in Row-Major Order
function displayRowMajor(N)
{
    let rm = new LTMatrix(N);
 
    // Generate the array in the
    // row-major form
    rm.setRowMajor(1, 1, 1);
    rm.setRowMajor(2, 1, 2);
    rm.setRowMajor(2, 2, 3);
    rm.setRowMajor(3, 1, 4);
    rm.setRowMajor(3, 2, 5);
    rm.setRowMajor(3, 3, 6);
    rm.setRowMajor(4, 1, 7);
    rm.setRowMajor(4, 2, 8);
    rm.setRowMajor(4, 3, 9);
    rm.setRowMajor(4, 4, 10);
 
    // Display array elements
    // in row-major order
    console.log("Row-Wise:");
    rm.Display(false);
}
 
// Function to generate and display
// array in Column-Major Order
function displayColMajor(N)
{
    let cm = new LTMatrix(N);
 
    // Generate array in
    // column-major form
    cm.setColMajor(1, 1, 1);
    cm.setColMajor(2, 1, 2);
    cm.setColMajor(2, 2, 3);
    cm.setColMajor(3, 1, 4);
    cm.setColMajor(3, 2, 5);
    cm.setColMajor(3, 3, 6);
    cm.setColMajor(4, 1, 7);
    cm.setColMajor(4, 2, 8);
    cm.setColMajor(4, 3, 9);
    cm.setColMajor(4, 4, 10);
 
    // Display array elements
    // in column-major form
    console.log("Column-Wise:");
    cm.Display(false);
}
 
// Driver Code
 
// Size of row or column
                        
// of square matrix
                        
let N = 4;
 
// Function Call for row major
// mapping
displayRowMajor(N);
 
// Function Call for column
// major mapping
displayColMajor(N);
 
// This code is contributed by phasing17

                  

              
            

输出：

行方面：
1 2 3 4 5 6 7 8 9 10
按列：
1 2 4 7 3 5 8 6 9 10

时间复杂度： O(N ² )
辅助空间： O(N ² )