# Sparse matrix calculation algorithm

Baidu Encyclopedia

Personal understanding: extract useful points from a matrix two-dimensional array and record them

Use scenario: chessboard

• 0 means no move
• 1 means sunspot
• 2 means Baizi

The checkerboard array before extraction is:

```0 0 	0 	0 	0 	0 	0 	0 	0 	0 	0 	0
0 	0 	1 	0 	0 	0 	0 	0 	0 	0 	0
0 	0 	0 	2 	0 	0 	0 	0 	0 	0 	0
0 	0 	0 	0 	0 	0 	0 	0 	0 	0 	0
0 	0 	0 	0 	0 	0 	0 	0 	0 	0 	0
0 	0 	0 	0 	0 	0	0 	0 	0 	0 	0
0 	0 	0 	0 	0 	0 	0 	0 	0 	0 	0
0 	0 	0 	0 	0 	0	0 	0 	0 	0 	0
0 	0 	0 	0 	0 	0 	0 	0 	0 	0 	0
0 	0 0	 0 	0 	0 	0 	0 	0 	0 	0 	0
0 	0 0 0 	0 	0 	0 	0 	0 	0 	0 	0 	0
duplicated code```

Sparse array after extraction:

```. 11 	. 11 	2
. 1 	2 	. 1
2 	. 3 	2
duplicated code```

Interpret the extracted sparse array:

• [0][0] The position is a two-dimensional array row

• [0][1] The position is a two-dimensional array column

• [0][2] The position is the total number of effective points (1 and 2) of the two-dimensional array

• [1][0] is the row coordinates of the first piece

• [1][1] is the coordinates of the first chess piece row

• [1][2] is the value of the first piece (1 means black)

By analogy, record the coordinates and values of all chess pieces on the board

Auxiliary diagram:

Summary: The sparse algorithm is also a two-dimensional array, the final number of rows is the total number +1, and the column is 3.

```    //countTemp + 1 row (countTemp a checkerboard currently valid number (number = 0)!)
//3 column
int SparseArray [] [] = new new  int [countTemp + . 1 ] [ 3 ];
duplicated code```

Auxiliary diagram:

# Create a two-dimensional array

Here is an example of a two-dimensional array of 11 * 11

```    //Row
public  static  int mRow = 11 ;
//column
public  static  int mColumn = 11 ;

//TODO creates the original two-dimensional array data
int chessArr1[][] = new  int [mRow][mColumn];

//Assign
chessArr1[ 1 ][ 2 ] = 1 to the black and white ; //1 is the black
chessArr1[ 2 ][ 3 ] = 2 ; //2 is the white
//chessArr1[5][2] = 1;

System.out.println( "The original two-dimensional array is:" );
for ( int i = 0 ; i <chessArr1.length; i++) {
for ( int j = 0 ; j <chessArr1[i].length; j++ ) {
System.out.printf( "%d\t" , chessArr1[i][j]);
}
System.out.println();
}
Copy code```

The results of the operation are:

```The original two-dimensional array is:
0 	0 	0 	0 	0 	0 	0 	0 	0 	0 	0
0 	0 	1 	0 	0 	0 	0 	0 	0 	0 	0
0 	0 	0 	2 	0 	0 	0 	0 	0 	0 	0
0 	0 	0 	0 	0 	0 	0 	0 	0 	0 	0
0 	0 	0 	0 	0 	0 	0 	0 	0 	0 	0
0 	0 	0 	0 0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
```

(!=0 )

```// !=0

int countTemp = 0;
//
for (int i = 0; i < mRow; i++) {
//
for (int j = 0; j < mColumn; j++) {
if (chessArr1[i][j] != 0) {
countTemp++;
}
}
}
System.out.println("  0   " + countTemp + " ");
```

# :

:

``` int sparseArray[][] = new  int [countTemp + 1][3];

//TODO assigns a value to the first row of the sparse array
//row
sparseArray[ 0 ][ 0 ] = mRow;
//column
sparseArray[ 0 ][ 1 ] = mColumn;
//total
sparseArray[ 0][2] = countTemp;
```

, !=0 :

```//Used to record the non-zero data
int countTemp2 = 0 ;
//Traverse the two-dimensional array and put the non-zero data in sparseArray[][]
for ( int i = 0 ; i <mRow; i++) {
//Traverse the column
for ( int j = 0 ; j <mColumn; j++) {
if (chessArr1[i][j] != 0 ) {
countTemp2++;
sparseArray[countTemp2][ 0 ] = i; //i = row
sparseArray[countTemp2][ 1 ] = j; //j = column
sparseArray[countTemp2][ 2 ] = chessArr1[i][j]; //chessArr1[ i][j] = specific value
}
}
}

//TODO output sparse array
System.out.println( "Sparse data is:" );
//traverse rows
for ( int i = 0 ; i <sparseArray.length; i++) {
//traverse columns
for ( int j = 0 ; j <sparseArray[i].length; j++) {
System.out.printf( "%d\t" , sparseArray[i][j]);
}
System.out.println();
}
Copy code```

The results of the sparse array operation are:

```Sparse data:
. 11 	. 11 	2
. 1 	2 	. 1
2 	. 3 	2
duplicated code```

# Sparse array to two-dimensional array

## Create a two-dimensional array

• Behavior sparse array [0][0] position
• Listed as sparse array [0][1] position
• The number of loops is the length of the two-dimensional array
```int array[][] = new  int [sparseArray[ 0 ][ 0 ]][sparseArray[ 0 ][ 1 ]];

System.out.println( "sparseArray.length" + sparseArray.length);
//The first line is the number of rows and columns of the original array, so traverse from the first line
for ( int i = 1 ; i <sparseArray.length; i++ ) {
/**
* Only loop with values, because int array[][] defaults to other values  as 0
* sparseArray[i][0] = row
* sparseArray[i][1] = column
* sparseArray[i][2] = value
*/
array[sparseArray[i][ 0 ]][sparseArray[i][ 1 ]] = sparseArray[i][ 2 ];
}

for ( int i = 0 ; i <array.length; i++) {
for ( int j = 0 ; j <array[i].length; j++) {
System.out.printf( "%d\t" , array[i][j]);
}
System.out.println();
}
Copy code```

The results of the operation are:

```sparseArray.length3
0 	0 	0 	0 	0 	0 	0 	0 	0 	0 	0
0 	0 	. 1 	0 	0 	0 	0 	0 	0 	0 	0
0 	0 	0 	2 	0 	0 	0 	0 	0 	0 	0
0 	0 	0 	0 	0 	0 	0 	0 	0 	0 	0
0 	0 	0 	0 	0 	0 	0 	0 	0 	0 	0
0 	0 	0 	0	0 	0 	0 	0 	0 	0 	0
0 	0 	0 	0 	0 	0 	0 	0 	0 	0 	0
0 	0 	0 	0 	0 	0 	0 	0 	0 	0 	0
0 	0 	0 	0 	0 	0 	0 	0 	0 	0 	0
0 	0 	0 	0 	0 	0 	0 	0 	0 	0 	0 0 0
0 	0 	0 	0 	0 	0 	0 	0 	0 	0	0
Copy the code```

Complete code

you may also like:

Data structure and algorithm catalog

Blogger homepage

Originality is not easy, your likes are your greatest support for me!