One , Sparse array

1, concept

When some elements in an array are 0, Or an array of the same value , You can use a sparse array to hold the data .

Processing method of sparse array :

* How many rows and columns does the record array have , How many different values are there ;
* Record the rows, columns and values of elements with different values in a small array , So as to reduce the scale of the program .
2, storage

* There are a lot of invalid data in the original array , It takes up a lot of storage space , Very little data is really useful ;
* Compressed storage can save storage space to avoid unnecessary waste of resources , When data is serialized to disk , Compressed storage can improve performance IO efficiency .

Two , Code instance
package com.atguigu.sparsearray; import java.io.File; import
java.io.FileReader; import java.io.FileWriter; public class SparseArray {
public static void sparseArrayToIO(int[][] sparseArr) throws Exception{
System.out.println(" Save sparse array to disk "); File file = new File("D:/sparseArr.txt");
if(!file.exists()){ file.createNewFile(); } FileWriter writer = new
FileWriter(file); for(int i =0; i < sparseArr.length; i++) { for(int j = 0; j <
3; j++) { writer.write(sparseArr[i][j]); } } writer.flush(); writer.close(); }
// Read sparse array from disk public static int[][] sparseArrFromIO(int lines) throws Exception
{ System.out.println(" Read sparse array from disk "); FileReader reader = new
FileReader("D:/sparseArr.txt"); int getNum = 0; int[][] sparseArray = new
int[lines][3]; for(int i = 0;i < lines;i++) { for (int j = 0; j < 3; j++) {
getNum = reader.read(); sparseArray[i][j] = getNum; } } return sparseArray; }
public static void ArrSparseArrTransfer() { // First, create an original two-dimensional array
//0 It means there are no pieces ,1 Represents a sunspot ,2 It means blue int chessArr1[][] = new int[11][11]; chessArr1[1][2] = 1;
chessArr1[2][3] = 2; // Output the original two-dimensional array System.out.println(" Original two-dimensional array "); for(int[] row :
chessArr1) { for(int data : row) { System.out.printf("%d\t",data); }
System.out.println(); } // The idea of transforming two dimensional array into sparse array //1, First traverse the two-dimensional array , Get non 0 Number of data int sum = 0;
for(int i = 0;i<11;i++) { for(int j = 0;j<11;j++) { if(chessArr1[i][j]!=0) {
sum++; } } } //2, Create a sparse array int sparseArr[][] = new int[sum+1][3]; //3, Sparse array assignment
sparseArr[0][0] = 11; sparseArr[0][1] = 11; sparseArr[0][2] = sum;
// Traversing two dimensional arrays , Will not be 0 To a sparse array int count = 0;//count It is used to record the number of non 0 data for(int i =
0;i<11;i++) { for(int j = 0;j<11;j++) { if(chessArr1[i][j]!=0) { count++;
sparseArr[count][0] = i; sparseArr[count][1] = j; sparseArr[count][2] =
chessArr1[i][j]; } } } // The form of output sparse array System.out.println(" Sparse array "); for(int[] row :
sparseArr) { for(int data : row) { System.out.printf("%d\t",data); }
System.out.println(); } int sparseArr2[][] = new int[sum+1][3]; try {
sparseArrayToIO(sparseArr); sparseArr2 = sparseArrFromIO(3); for(int[] row :
sparseArr2) { for(int data : row) { System.out.printf("%d\t",data); }
System.out.println(); } } catch (Exception e) { e.printStackTrace(); }
// The sparse array is restored to the original two-dimensional array //1, Read the first row of the sparse array first , According to the data in the first line , Create the original two-dimensional array int chessArr2[][] = new
int[sparseArr2[0][0]][sparseArr2[0][1]]; //2, Then read the data of the last few rows of the sparse array ( Start with the second line ), And assign it to the original two-dimensional array
for(int i = 1;i<sparseArr2.length;i++) {
chessArr2[sparseArr2[i][0]][sparseArr2[i][1]] = sparseArr2[i][2]; } // 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(); } } public
static void main(String[] args) { ArrSparseArrTransfer(); } }
Three , console output

 

Technology
©2019-2020 Toolsou All rights reserved,
TP6 Application examples of verifier and correct verification data ESP8266/ESP32 System : Optimize system startup time 2021 year 2 Chinese programming language ranking 2021 year 1 Monthly programmer salary statistics , average 14915 element CSS architecture design It's not depravity that's terrible , It's about knowing you're falling Gude Haowen serial - You deserve to be an engineer ( Preface ) Software testing BUG describe C Course design of language programming of 《 Student achievement management system 》vue In the project axios Global encapsulation of