What is a sparse array

When most elements of array A are 0, or the same value, then we can use sparse array B to store array A.

First, the sparse array is an array, and then the array A is stored in a specific way:

  • The record array A has several rows and columns
  • Record how many different values there are in A
  • Finally, the columns and columns of the elements with different values, as well as the specific values, are placed in a small array to reduce the size of the program.

This small array is called a sparse array.

For example, on the left is a two-dimensional array with five rows and four columns, and six non-zero values. As a result, the rule can be converted to the sparse array on the right.

Ii. Scene usage

I get the point, but what are the scenarios for this? For example, there is a program requirement for a backgammon game: the game can be saved, and the next time you open the game, you can continue the game.

So record the board content of backgammon, in fact, with a two-dimensional array record is very intuitive.

But because many of the values in this two-dimensional array are 0, it makes no sense to consider converting it with a sparse array.

1. Two-dimensional array to sparse array idea

The idea is simple:

  1. Iterate through the original two-dimensional array to get the number of valid data sum
  2. From sum we can create a sparse array called sparseArr
  3. Store valid data from a two-dimensional array into a sparse array

2. Sparse array to two-dimensional array idea

When reading a disk, we need to convert the sparse array back to a two-dimensional array:

  1. First read the first row of the sparse array, and create a two-dimensional array according to the data in the first row
  2. Continue reading the next few lines of the sparse array and assign to the two-dimensional array.

3. Code implementation

The process is simple, by the way, sparse arrays are best saved on disk (not included in the code) and then read and converted back to two-dimensional arrays when needed.

Public class SparseArray {public static void main(String[] args) {public static void main(String[] args) { Int chessArr1[][] = new int[11][11]; chessArr1[1][2] = 1; chessArr1[2][3] = 2; For (int[] row: chessArr1) {for (int data: row) {system.out.printf ("%d\t", data); for (int data: chessArr1) {system.out.printf ("%d\t", data); } System.out.println(); Int sum = 0; int sum = 0; for (int i = 0; i < chessArr1.length; i++) { for (int j = 0; j < chessArr1.length ; j++) { if (chessArr1[i][j] ! = 0) { sum++; } } } System.out.println("sum: " + sum); Int sparseArr[][] = new int[sum+1][3]; // Assign sparseArr[0][0] = 11; sparseArr[0][1] = 11; sparseArr[0][2] = sum; SparseArr int count = 0; For (int I = 0; i < chessArr1.length; i++) { for (int j = 0; j < chessArr1.length ; j++) { if (chessArr1[i][j] ! = 0) { count++; sparseArr[count][0] = i; sparseArr[count][1] = j; sparseArr[count][2] = chessArr1[i][j]; System.out.println(" Sparse array: "); for (int i = 0; i < sparseArr.length; i++) { System.out.printf("%d\t%d\t%d\t\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]); } System.out.println(); 1. Read the first row of the sparse array. According to the data in the first row, Int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]]; Int I = 1; for (int I = 1; i < sparseArr.length; i++) { chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2]; } // Output the restored 2d array system.out.println (" restored 2D array: "); for (int[] row : chessArr2) { for (int data : row) { System.out.printf("%d\t", data); } System.out.println(); }}}Copy the code

Running results:

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 sum: 2 Sparse array: 11 11 2 1 2 1 2 1 2 3 2 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 Process finished with exit code 0Copy the code