대칭 행렬 압축 저장 애니메이션 데모

给定一个下三角矩阵 Mat[][] ，任务是使用行主映射来存储矩阵。

下三角矩阵： 下三角矩阵是一个方阵，其中矩阵的下三角部分由非零元素组成，上三角部分由 0 组成。二维矩阵 Mat[][] 的下三角矩阵在数学上定义为：

如果 i < j ，则设置 Mat[i][j] = 0 。
如果 i >= j ，则设置 Mat[i][j] > 0 。

说明： 下面是一个 5×5 的下三角矩阵。一般来说，这样的矩阵可以存储在二维数组中，但是当涉及到大尺寸的矩阵时，它不是一个好的选择，因为由于存储了不需要的 0 而导致内存消耗很高。
这样的矩阵可以以优化的方式实现。

存储大小为 N的下三角矩阵的有效方法：

非零元素的计数 = 1 + 2 + 3 + … + N = N * (N + 1) /2 。
0 的计数 = N ² – (N * (N + 1) /2 = (N * (N – 1)/2 。

现在让我们看看如何在程序中表示下三角矩阵。请注意，必须避免存储 0 ，以减少内存消耗。 经计算，存储非零元素需要 N*(N+1)/2空间。 以上面的例子为例， N = 5 。需要大小为 5 * (5 + 1)/2 = 15 的 数组来存储非零元素。

现在，二维矩阵的元素可以逐行存储在一维数组中，如下所示：

除了将元素存储在数组中之外，还需要一个提取行号和列号对应的元素的过程。
使用行主映射来存储下三角矩阵，索引 Mat[i][j] 处的元素可以表示为：

数组 A[] 中 Mat[i][j] 矩阵的索引= [i*(i – 1)/2 + j – 1]

下面是上述方法的实现：

C++

              
                
                    // C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Dimensions of a matrix
                        
static int N = 5;
 
// Structure of the efficient matrix
class Matrix {
  public:
  int* A;
  int size;
};
 
// Function to set the
                        
// values in the Matrix
                        
void Set(Matrix mat, int i, int j, int x)
                        
{
  if (i >= j)
    mat.A[i * (i - 1) / 2 + j - 1] = x;
}
 
// Function to store the
                        
// values in the Matrix
                        
int Get(Matrix mat, int i, int j)
                        
{
  if (i >= j)
    return mat.A[i * (i - 1) / 2 + j - 1];
  return 0;
}
 
// Function to display the
                        
// elements of the matrix
                        
void Display(Matrix mat)
{
  int i, j;
  // Traverse the matrix
  for (i = 1; i <= mat.size; i++) {
                        
    for (j = 1; j <= mat.size; j++) {
                        
      if (i >= j)
        cout << mat.A[i * (i - 1) / 2 + j - 1]
        << " ";
                        
      else
        cout << 0 << " ";
    }
    cout << endl;
  }
}
 
// Function to generate an efficient matrix
Matrix createMat(vector<vector<int> >& Mat)
{
  // Declare efficient Matrix
  Matrix mat;
  // Initialize the Matrix
  mat.size = N;
  mat.A = new int[(mat.size * (mat.size + 1)) / 2];
                        
  int i, j;
  // Set the values in matrix
  for (i = 1; i <= mat.size; i++)
                        
    for (j = 1; j <= mat.size; j++)
                        
      Set(mat, i, j, Mat[i - 1][j - 1]);
  // Return the matrix
  return mat;
}
 
// Driver Code
int main()
{
  vector<vector<int> > Mat = { { 1, 0, 0, 0, 0 },
                              { 1, 2, 0, 0, 0 },
                              { 1, 2, 3, 0, 0 },
                              { 1, 2, 3, 4, 0 },
                              { 1, 2, 3, 4, 5 } };
 
  // Stores the efficient matrix
  Matrix mat = createMat(Mat);
   
                        
  // Print the Matrix
  Display(mat);
  return 0;
}
 
// This code is contributed by Tapesh (tapeshdua420)

                  

              
            

C

              
                
                    // C program for the above approach
#include <stdio.h>
                        
#include <stdlib.h>
 
// Dimensions of a matrix
                        
const int N = 5;
 
// Structure of the efficient matrix
struct Matrix {
    int* A;
    int
                          size;
};
 
// Function to set the
                        
// values in the Matrix
                        
void Set(struct Matrix* mat,
         int i, int j, int x)
{
    if
                          (i >= j)
        mat->A[i * (i - 1) / 2 + j - 1] = x;
}
 
// Function to store the
                        
// values in the Matrix
                        
int Get(struct Matrix mat, int i, int j)
                        
{
    if
                          (i >= j) {
        return mat.A[i * (i - 1) / 2 + j - 1];
    }
    else {
        return 0;
    }
}
 
// Function to display the
                        
// elements of the matrix
                        
void Display(struct Matrix mat)
{
    int
                          i, j;
 
    // Traverse the matrix
    for (i = 1; i <= mat.size; i++) {
                        
        for (j = 1; j <= mat.size; j++) {
                        
 
            if (i >= j) {
                printf("%d ",
                       mat.A[i * (i - 1) / 2 + j - 1]);
            }
            else {
                printf("0 ");
            }
        }
        printf("\n");
    }
}
 
// Function to generate an efficient matrix
struct Matrix createMat(int Mat[N][N])
{
    // Declare efficient Matrix
    struct Matrix mat;
 
    // Initialize the Matrix
    mat.size = N;
    mat.A = (int*)malloc(
        mat.size * (mat.size + 1) / 2
        * sizeof(int));
                        
 
    int
                          i, j;
 
    // Set the values in matrix
    for (i = 1; i <= mat.size; i++) {
                        
 
        for (j = 1; j <= mat.size; j++) {
                        
 
            Set(&mat, i, j, Mat[i - 1][j - 1]);
        }
    }
 
    // Return the matrix
    return mat;
}
 
// Driver Code
int main()
{
    int
                          Mat[5][5] = { { 1, 0, 0, 0, 0 },
                      { 1, 2, 0, 0, 0 },
                      { 1, 2, 3, 0, 0 },
                      { 1, 2, 3, 4, 0 },
                      { 1, 2, 3, 4, 5 } };
 
    // Stores the efficient matrix
    struct Matrix mat = createMat(Mat);
                        
 
    // Print the Matrix
    Display(mat);
 
    return 0;
}

                  

              
            

Java

              
                
                    // Java program for the above approach
class GFG
{
   
                        
// Dimensions of a matrix
                        
static int N = 5;
 
// Structure of the efficient matrix
static class Matrix {
    int[] A;
    int
                          size;
};
 
// Function to set the
                        
// values in the Matrix
                        
static void Set(Matrix mat,
         int i, int
                          j, int x)
                        
{
    if
                          (i >= j)
        mat.A[i * (i - 1) / 2 + j - 1] = x;
}
 
// Function to store the
                        
// values in the Matrix
                        
static int Get(Matrix mat, int i, int
                          j)
{
    if
                          (i >= j) {
        return mat.A[i * (i - 1) / 2 + j - 1];
    }
    else
                          {
        return 0;
    }
}
 
// Function to display the
                        
// elements of the matrix
                        
static void Display(Matrix mat)
{
    int
                          i, j;
 
    // Traverse the matrix
    for
                          (i = 1; i <= mat.size; i++) {
        for (j = 1; j <= mat.size; j++) {
 
            if (i >= j) {
                System.out.printf("%d ",
                       mat.A[i * (i - 1) / 2 + j - 1]);
            }
            else {
                System.out.printf("0 ");
            }
        }
        System.out.printf("\n");
    }
}
 
// Function to generate an efficient matrix
static Matrix createMat(int Mat[][])
{
   
                        
    // Declare efficient Matrix
    Matrix mat = new Matrix();
 
    // Initialize the Matrix
    mat.size = N;
    mat.A = new int[(mat.size*(mat.size + 1)) / 2];
    int
                          i, j;
 
    // Set the values in matrix
    for
                          (i = 1; i <= mat.size; i++)
    {
        for (j = 1; j <= mat.size; j++)
        {
            Set(mat, i, j, Mat[i - 1][j - 1]);
        }
    }
 
    // Return the matrix
    return
                          mat;
}
 
// Driver Code
public static void main(String[] args)
{
    int
                          Mat[][] = { { 1, 0, 0, 0, 0 },
                      { 1, 2, 0, 0, 0 },
                      { 1, 2, 3, 0, 0 },
                      { 1, 2, 3, 4, 0 },
                      { 1, 2, 3, 4, 5 } };
 
    // Stores the efficient matrix
    Matrix mat = createMat(Mat);
 
    // Print the Matrix
    Display(mat);
}
}
 
// This code is contributed by 29AjayKumar

                  

              
            

Python3

              
                
                    # Python program for the above approach
 
# Dimensions of a matrix
                        
N = 5
 
# Structure of the efficient matrix
class Matrix:
    def
                          __init__(self, size):
        self.size =
                          size
        self.A = [None] * (self.size)
 
# Function to set the
                        
# values in the Matrix
                        
def Set(mat, i, j, x):
    if
                          i >= j:
                        
        mat.A[i * (i - 1) // 2 + j - 1] = x
 
# Function to store the
                        
# values in the Matrix
                        
def get(mat, i, j):
    if
                          i >= j:
                        
        return mat.A[i * (i - 1) // 2 + j - 1]
    return
                          0
 
# Function to display the
                        
# elements of the matrix
                        
def display(mat):
    # Traverse the matrix
    for
                          i in range(1, mat.size + 1):
        for j in
                          range(1, mat.size +
                          1):
            if i >=
                          j:
                print(mat.A[i * (i - 1) // 2 + j - 1], end=" ")
            else:
                print(0, end=" ")
        print()
 
# Function to generate an efficient matrix
def create_matrix(Mat):
    # Declare efficient Matrix
    mat = Matrix(N)
    # Initialize the Matrix
    mat.A = [None] * ((mat.size * (mat.size+1)) // 2)
    # Set the values in matrix
    for
                          i in range(1, mat.size + 1):
        for j in
                          range(1, mat.size +
                          1):
            Set(mat, i, j, Mat[i - 1][j - 1])
    # Return the matrix
    return
                          mat
 
 
if __name__ ==
                          '__main__':
 
    Mat = [[1, 0, 0, 0, 0],
           [1, 2, 0, 0, 0],
           [1, 2, 3, 0, 0],
           [1, 2, 3, 4, 0],
           [1, 2, 3, 4, 5]]
 
    mat = create_matrix(Mat)
    display(mat)
 
# This code is contributed by Tapesh (tapeshdua420)

                  

              
            

C＃

              
                
                    // C# program for the above approach
using System;
public class GFG
{
 
  // Dimensions of a matrix
  static int N = 5;
 
  // Structure of the efficient matrix
  class Matrix {
    public
                          int[] A;
    public
                          int size;
  };
 
  // Function to set the
  // values in the Matrix
  static void Set(Matrix mat,
                  int i, int
                          j, int x)
                        
  {
    if
                          (i >= j)
      mat.A[i * (i - 1) / 2 + j - 1] = x;
  }
 
  // Function to store the
  // values in the Matrix
  static int Get(Matrix mat, int i, int j)
  {
    if
                          (i >= j) {
      return mat.A[i * (i - 1) / 2 + j - 1];
                        
    }
    else
                          {
      return 0;
    }
  }
 
  // Function to display the
  // elements of the matrix
  static void Display(Matrix mat)
  {
    int
                          i, j;
 
    // Traverse the matrix
    for
                          (i = 1; i <= mat.size; i++) {
      for (j = 1; j <= mat.size; j++) {
 
        if (i >= j) {
          Console.Write("{0} ",
                        mat.A[i * (i - 1) / 2 + j - 1]);
        }
        else {
          Console.Write("0 ");
        }
      }
      Console.Write("\n");
    }
  }
 
  // Function to generate an efficient matrix
  static Matrix createMat(int [,]Mat)
  {
 
    // Declare efficient Matrix
    Matrix mat = new Matrix();
 
    // Initialize the Matrix
    mat.size = N;
    mat.A = new int[(mat.size*(mat.size + 1)) / 2];
    int
                          i, j;
 
    // Set the values in matrix
    for
                          (i = 1; i <= mat.size; i++)
    {
      for (j = 1; j <= mat.size; j++)
      {
        Set(mat, i, j, Mat[i - 1,j - 1]);
      }
    }
 
    // Return the matrix
    return
                          mat;
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int
                          [,]Mat = { { 1, 0, 0, 0, 0 },
                  { 1, 2, 0, 0, 0 },
                  { 1, 2, 3, 0, 0 },
                  { 1, 2, 3, 4, 0 },
                  { 1, 2, 3, 4, 5 } };
 
    // Stores the efficient matrix
    Matrix mat = createMat(Mat);
 
    // Print the Matrix 
    Display(mat);
  }
}
 
// This code is contributed by 29AjayKumar

                  

              
            

JavaScript

              
                
                    // JavaScript program for the above approach
 
let N = 5;
 
class Matrix{
    A = new Array();
    size;
                        
    constructor(){ }
}
 
function Set(mat, i, j, x){
    if
                          (i >= j){
        mat.A[i * (i - 1) / 2 + j - 1] = x;
    }
}
 
function Get(mat, i, j){
    if
                          (i >= j) {
        return mat.A[i * (i - 1) / 2 + j - 1];
                        
    }
    else
                          {
        return 0;
    }
}
 
function Display(mat){
    let i, j;
                        
     
    // Traverse the matrix
    for
                          (i = 1; i <= mat.size; i++) {
        for (j = 1; j <= mat.size; j++) {
 
            if (i >= j) {
                console.log(mat.A[i * (i - 1) / 2 + j - 1] + " ");
            }
            else {
                console.log("0 ");
            }
        }
        console.log("<br>");
    }
}
 
function createMat(Mat){
    var
                          mat = new Matrix();
     
    mat.size = N;
     
    mat.A = new Array((mat.size*(mat.size + 1))/2);
    let i, j;
                        
     
    // Set the values in matrix
    for
                          (i = 1; i <= mat.size; i++)
    {
        for (j = 1; j <= mat.size; j++)
        {
            Set(mat, i, j, Mat[i - 1][j - 1]);
        }
    }
 
    // Return the matrix
    return
                          mat;
}
 
let Mat = [ [1, 0, 0, 0, 0],
                        
               [1, 2, 0, 0, 0],
               [1, 2, 3, 0, 0],
               [1, 2, 3, 4, 0],
               [1, 2, 3, 4, 5] ];
 
var mat = createMat(Mat);
Display(mat);
 
// This code is contributed by lokesh.

                  

              
            

输出：

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