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!