This is the fourth day of my participation in the August Challenge. For details, see:August is more challenging
preface
When writing LeetCode, I feel that my knowledge of data structure and algorithm is not strong enough, and it is absolutely not good to learn the algorithm! So go to some station to find the video of data structure and algorithm to learn, and check the leak to fill the gap. Today’s lesson is from understand to learn to master sparse arrays ~
The sparse array
Sparse Array
When to use it
When most of the elements in an array are zeros, or an array with the same value, you can use a sparse array to hold the array,
Processing method
1) Keep track of how many rows and columns the array has and how many different values it has
2) Reduce the size of the program by recording the rows, columns, and values of elements with different values in a small array
For example
Turn it into a sparse array ↓
Turn to sparse array ideas
The idea of turning a two-dimensional array into a sparse array
-
Iterating over the original 2d array to get the total number of valid data, sum
-
SparseArr int[sum + 1] [3] sparseArr int[sum + 1] [3] sparseArr int[sum + 1]
-
Store valid data from a two-dimensional array into a sparse array
The idea of turning a sparse array into a primitive two-dimensional array
-
First read the first row of the sparse array, according to the data in the first row, get the number of rows and columns of the array, and create the original two-dimensional array, such as chessArr2 = int[11] [11] above.
-
After reading the sparse array a few rows of data, and assign to the original two-dimensional array
Code implementation
Public class SparseArray{public static void main(String[] args){// create an original two-dimensional array. Int chessArr1[] [] = new int [11] [11]; chessArr1[1] [2] = 1; chessArr1[2] [3] = 1; Println (" the original two-dimensional array "); // Output the original two-dimensional array system.out.println (" the original two-dimensional array "); for(int[] row : chessArr1){ for(int data : row){ System.out.printf("%d\t",data); Int sum = 0; int sum = 0; for(int i = 0; i < chessArr1.length; i++){ for(int j = 0; j < chessArr1.length ; j++){ if(chessArr[i] [j] ! = 0){ sum++; Int sparseArr[] [] = new int[sum+1] [3]; SparseArr [0] [0] = 11; sparseArr[0] [1] = 11; sparseArr[0] [2] = sum; Int count = 0; sparseArr = sparseArr int count = 0; For (int I = 0; i<chessArr1.length; i++){ for(int j = 0; j < chessArr1.length ; j++){ count ++; if(chessArr[i] [j] ! = 0){ sparseArr[count] [0] = i; sparseArr[count] [1] = j; sparseArr[count] [2] = chessArr1[i] [j]; }}} // Output the sparse array form system.out.println (); System.out.println(" get sparse array as "); for(int i = 0; i < sparseAr.length; i++){ System.out.printf("%d\t%d\t%d\t",sparseArr[i] [0],sparseArr[i] [1],sparseArr[i] [2]); } System.out.println(); Int chessArr2[] [] = new int [sparseArr[0] [0]] [sparseArr[0] [1]]; for( int i = 1 ; i < sparseArr.length ; i++){ chessArr2[sparseArr[i] [0]] [sparseArr[i] [1]] = sparseArr[i] [2]; } // Output the restored two-dimensional array system.out.println (); System.out.println(" restored two-dimensional array "); for(int[] row: chessArr2){ for(int data: row){ System.out.printf("%d\t",data); } System.out.println(); }}}Copy the code
The article has the bad place that writes, still ask big guy people not stingy give instruction!!
Tomorrow also want to continue refueling duck!