Sparse array (sparse)

1. Basic introduction

When most of the elements in an array are 0, Or an array of the same value , You can save the array using a sparse array

2. Sparse array processing method

1） There are several rows and columns in the record array

2） Record the row and column values of elements with different values in a small array , To reduce the size of the program

3. Two dimensional array to sparse array

1） Traversing the original two-dimensional array , Number of valid data obtained sum

2) according to sum You can create a sparse array sparseArr int [sum+1][3]

3) Store the valid data of a two-dimensional array into a sparse array

package com.lin.sparsearray;
/*
 *  Checkerboard storage ： Sunspots are in the second row and third column of the chessboard , Baizi is in the third row and the fourth column 
 *  Two dimensional array to sparse array 
 * 1） Traversing the original two-dimensional array , Number of valid data obtained sum

   2) according to sum You can create a sparse array sparseArr int [sum+1][3]

   3) Store the valid data of a two-dimensional array into a sparse array 
 * 
 * 
 * */

public class SparseArray {

	public static void main(String[] args) {
//		 Create an original array 11*11
//		0： No chess pieces ,1 Said the spots ,2 Said an albino 
		int chessArr1[][]=new int[11][11];
//		 The position of sunspots in the original array 
		chessArr1[1][2]=1;
//		 The position of the white child in the original array 
		chessArr1[2][3]=2;
		System.out.println(" The original two-dimensional array ：");
//		 Output the original two-dimensional array 
		for(int arr[]:chessArr1) {
			for(int data:arr) {
				System.out.printf("%d\t",data);
			}
			System.out.println();
		}
		
		// Convert a two-dimensional array to a sparse array 
		//1. First, traverse the two-dimensional array   Get the blame 0 Number of data 
		int sum=0;// The record is not 0 Number of data 
		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);
		//2. Create the corresponding sparse array 
		int sparseArr[][]=new int[sum+1][3];
		// Assign values to sparse arrays 
		sparseArr[0][0]=11;
		sparseArr[0][1]=11;
		sparseArr[0][2]=sum;
		
		int count=0;// It's the number one non 0 data 
		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];
				}
			}
		}
		
//		 Output sparse array form 
		System.out.println();
		System.out.println(" The sparse array is ：");
		for(int i=0;i<sparseArr.length;i++) {
			for(int j=0;j<3;j++) {
				System.out.print(sparseArr[i][j]+"	");
			}
			System.out.println();	
		}
	}

}

4. The idea of transforming sparse array into original two-dimensional array

1） First read the first row of the sparse array , According to the data in the first line , Create the original two-dimensional array

2） After reading the sparse array a few lines of data , And assign it to the original two-dimensional array

package com.lin.sparsearray;
/*
 *  Checkerboard storage ： Sunspots are in the second row and third column of the chessboard , Baizi is in the third row and the fourth column 
 *  Two dimensional array to sparse array 
 * 1） Traversing the original two-dimensional array , Number of valid data obtained sum

   2) according to sum You can create a sparse array sparseArr int [sum+1][3]

   3) Store the valid data of a two-dimensional array into a sparse array 
 * 
 * 
 * */

public class SparseArray {

	public static void main(String[] args) {
//		 Create an original array 11*11
//		0： No chess pieces ,1 Said the spots ,2 Said an albino 
		int chessArr1[][]=new int[11][11];
//		 The position of sunspots in the original array 
		chessArr1[1][2]=1;
//		 The position of the white child in the original array 
		chessArr1[2][3]=2;
		System.out.println(" The original two-dimensional array ：");
//		 Output the original two-dimensional array 
		for(int arr[]:chessArr1) {
			for(int data:arr) {
				System.out.printf("%d\t",data);
			}
			System.out.println();
		}
		
		// Convert a two-dimensional array to a sparse array 
		//1. First, traverse the two-dimensional array   Get the blame 0 Number of data 
		int sum=0;// The record is not 0 Number of data 
		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);
		//2. Create the corresponding sparse array 
		int sparseArr[][]=new int[sum+1][3];
		// Assign values to sparse arrays 
		sparseArr[0][0]=11;
		sparseArr[0][1]=11;
		sparseArr[0][2]=sum;
		
		int count=0;// It's the number one non 0 data 
		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];
				}
			}
		}
		
//		 Output sparse array form 
		System.out.println();
		System.out.println(" The sparse array is ：");
		for(int i=0;i<sparseArr.length;i++) {
			for(int j=0;j<3;j++) {
				System.out.print(sparseArr[i][j]+"	");
			}
			System.out.println();	
		}
		
		/*
		 *  Convert the sparse array to the original array 
		 * 1） First read the first row of the sparse array , According to the data in the first line , Create the original two-dimensional array 
		   2） After reading the sparse array a few lines of data , And assign it to the original two-dimensional array 
		 * 
		 * */
//		1） First read the first row of the sparse array , According to the data in the first line , Create the original two-dimensional array 
		int chessArr2[][]=new int[sparseArr[0][0]][sparseArr[0][1]];
		
		
//		2） After reading the sparse array a few lines of data , And assign it to the original two-dimensional array 
		System.out.println();
		System.out.println(" Recovered 2D array ：");
		
		for(int i=1;i<sparseArr.length;i++) {
			chessArr2[sparseArr[i][0]][sparseArr[i][1]]=sparseArr[i][2];
		}
		for(int arr[]:chessArr2) {
			for(int data:arr) {
				System.out.printf("%d\t",data);
			}
			System.out.println();
		}
	}

}