Sparse array [matrix]

Sparse array

 

1. first line ： Record the original array, which has several rows and columns , Several different values
2. Residual downlink ： Record the rows, columns and values of elements with different values in an array , To reduce the size of the program

  Two dimensional array   turn   The idea of sparse array

1. Traverse Original two-dimensional array , Get the number of valid data sum

2. according to sum establish Sparse array sparseArr int[sum+1][3]   3 It must be the same

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

Sparse array to original two-dimensional array idea  

1. First read the first two data in the first row of the sparse array Create the original two-dimensional array

2. Read the data of the last few rows of the sparse array And assign it to the original array

public class T1 {
    public static void main(String[] args) {
        // Compress a two-dimensional array into a sparse array 
        //1. Create a 2D array 
        int chessArr[][] = new int[11][11];
        chessArr[1][2] = 1;
        chessArr[2][3] = 2;
        int sum = 0;
        //2. Get the number of valid data 
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++)
                if (chessArr[i][j] != 0)
                    sum++;
        }
        //3. Create a sparse array 
        int spareArr[][] = new int[sum+1][3];
        spareArr[0][0] = 11;
        spareArr[0][1] = 11;
        spareArr[0][2] = sum;
        //4. assignment 
        int count = 0;
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (chessArr[i][j] != 0){
                    count++;
                    spareArr[count][0] = i ;
                    spareArr[count][1] = j ;
                    spareArr[count][2] = chessArr[i][j] ;
                }
            }
        }
        System.out.println(" Output sparse array ");
        for (int i=0;i<spareArr.length;i++)
            System.out.printf("%d\t%d\t%d\t\n",spareArr[i][0],spareArr[i][1],spareArr[i][2]);

        System.out.println("==============");
        // Sparse array to two-dimensional array 
        //1. Read the first two data of the first row of the sparse array , Then create a new two-dimensional array 
        int chessArr1[][] = new int[spareArr[0][0]][spareArr[0][1]];
        //2. Traverse the second row of the sparse array, followed by , Then assign a value to a two-dimensional array 
        for (int i = 1;i< spareArr.length;i++){
            chessArr1[spareArr[i][0]][spareArr[i][1]] = spareArr[i][2];
        }
        //3. Output two-dimensional array 
        for (int[] row : chessArr1){
            for (int data :row){
                System.out.printf("%d\t",data);
            }
            System.out.println();
        }
    }
}

Save sparse arrays to disk , And restore 【 New function 】

Save sparse array

// Read to disk 
        // Get file object 
        File file = new File("E:\\map.data");
        // File write stream 
        FileWriter writer = new FileWriter(file);
        // Traversal array , write file 
        for (int[] sparse:sparseArr) {
            for (int s:sparse) {
                writer.write(s+"\t");
            }
            writer.write("\n");
        }
        writer.close();

Restore sparse array

 // Read data from disk 
        BufferedReader reader = new BufferedReader(new FileReader(file));
        String line = "";
        int[][] chessArr2 = null;
        int row = 0;

        // Loop through every line of the file 
        while ((line=reader.readLine())!=null){
            // Press tab Bits are cut into string arrays , And then to int Array 
            String[] temp = line.split("\t");
            int[] ints = new int[temp.length];
            for (int i = 0; i < ints.length; i++) {
                ints[i] = Integer.parseInt(temp[i]);
            }
            row++;
            // The first line of the document , That is, the first row of the sparse array , Is the length and width of the original array 
            if (row==1){
                chessArr2 = new int[ints[0]][ints[1]];
            }else{
                // Add the rest , Where there is no assignment , The array will be initialized to 0
                chessArr2[ints[0]][ints[1]] = ints[2];
            }
        }
        reader.close();
    }