Sparse matrix algorithm of java data structure and algorithm

Sparse matrix algorithm of java data structure and algorithm

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!