Sparse matrix algorithm

Baidu encyclopedia

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

Usage scenario: checkerboard

  • 0 indicates that no chess piece is moved
  • 1 means a spot
  • 2 is white

The checkerboard array before extraction 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
Copy the code

Sparse array after extraction:

11	11	2	
1	2	1	
2	3	2	
Copy the code

Read the extracted sparse array:

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

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

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

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

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

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

Analogize in turn, record all the chess pieces of the board’s coordinates and values

Auxiliary graph:

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

    CountTemp + 1 is a line (countTemp is a valid number in the current board (! = 0))
    / / 3 for the column
 int sparseArray[][] = new int[countTemp + 1] [3];
Copy the code

Auxiliary graph:

Creating a two-dimensional array

Here, take an 11 by 11 two-dimensional array

    / / line
    public static int mRow = 11;
    / / column
    public static int mColumn = 11;

  //TODO creates raw 2d array data
        int chessArr1[][] = new int[mRow][mColumn];

        // Assign values to black and white
        chessArr1[1] [2] = 1;/ / 1 for the spots
        chessArr1[2] [3] = 2;/ / 2 for an albino
// 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 the code

The running results are as follows:

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	
Copy the code

From a two-dimensional array to a sparse array

Start by recording all the pieces in the board (! The number of = 0)

// Get all the pieces in the board first! The number of = 0

 int countTemp = 0;
        / / traverse line
        for (int i = 0; i < mRow; i++) {
            / / traverse
            for (int j = 0; j < mColumn; j++) {
                if(chessArr1[i][j] ! =0) {
                    countTemp++;
                }
            }
        }
        System.out.println("There are non-zero numbers." + countTemp + "个");
Copy the code

Create a sparse array:

Assign the first line:

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

        //TODO assigns the first row of the sparse array
        / / line
        sparseArray[0] [0] = mRow;
        / / column
        sparseArray[0] [1] = mColumn;
        / / the total number of
        sparseArray[0] [2] = countTemp;
Copy the code

Loop two dimensional array, will! The value of =0 is assigned to the sparse array and printed:

// Record the number of non-zero data points
        int countTemp2 = 0;
        // Iterate over the two-dimensional array, placing non-zero data in sparseArray[][]
        for (int i = 0; i < mRow; i++) {
            / / traverse
            for (int j = 0; j < mColumn; j++) {
                if(chessArr1[i][j] ! =0) {
                    countTemp2++;
                    sparseArray[countTemp2][0] = i;/ / I = line
                    sparseArray[countTemp2][1] = j;/ / j = column
                    sparseArray[countTemp2][2] = chessArr1[i][j];//chessArr1[I][j] = specific value}}}//TODO outputs a sparse array
        System.out.println("The sparse data is :");
        / / traverse line
        for (int i = 0; i < sparseArray.length; i++) {
            / / traverse
            for (int j = 0; j < sparseArray[i].length; j++) {
                System.out.printf("%d\t", sparseArray[i][j]);
            }
            System.out.println();
        }
Copy the code

The running result of the sparse array is:

The sparse data is:11	11	2	
1	2	1	
2	3	2	
Copy the code

Sparse array to two-dimensional array

Creating a two-dimensional array

  • Behavior sparse array [0][0] position
  • Column in the sparse array [0][1] position
  • The number of cycles 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 in the original array
        for (int i = 1; i < sparseArray.length; i++) {
            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 the code

The running results are as follows:

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	
Copy the code

The complete code

What do you like?

Data structures and algorithms directory

Blogger page

Original is not easy, your praise is the biggest support for me!