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!