Day18 creation and restoration of sparse array

Sparse array

Record the coordinates and values of the valid values

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

Sparse array processing ：

• There are several rows and columns in the record array , How many different values
• Record elements, rows, columns and values with different values in a small array , So as to reduce the scale of the program .

Pictured

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-p8BKZLLM-1646094194934)(1645884023838.png)]

Operation steps

How to compress into a sparse array

1. First count the number of elements in the array
2. Create a sparse array again That's ok Column value , Remember that the number of rows is a statistical value +1（ Look up ）, Remember to assign the total number of header rows , Sum of columns
3. Traversal again does not mean 0 Value , Get the number of rows and the number of columns and values

How to decompress a sparse array

1. The first value of the first row of the sparse array is the row of the original array , The second value in the first row is the column of the original array , The third value in the first row is the value of the original array

package com.ckw.blog.arrays;

public class arrayxishu02 {
    
    public static void main(String[] args) {
    
        int[][] array =new int[11][11];
        array[1][3] = 8;
        array[3][7] = 21;
        array[5][2] = 12;
        array[6][3] = 45;
        array[10][9] = 67;
        // Created an array 
        for (int i = 0; i < array.length; i++) {
    
            for (int j = 0; j < array[i].length; j++) {
    
                System.out.print(array[i][j]+"\t");
            }
            System.out.println();
        }
        System.out.println("=============================");
        //1. Get the sum of the values in the array 
        int count = 0;// Counter 
        for (int i = 0; i < array.length; i++) {
    
            for (int j = 0; j < array[i].length; j++) {
    
                if(array[i][j]!=0){
    
                    count++;
                }
            }
        }
        //2. Create a two-dimensional sparse array . That's ok   Column   value . Remember that the number of rows is a statistical value +1（ Look up ）, Remember to assign the total number of header rows , Sum of columns 
        int[][] array02 = new int[count+1][3]; // Remember to add 1 As header 
        array02[0][0] =array.length;
        array02[0][1] =array[0].length;
        array02[0][2] =count;
        int nub = 0;
        //3.  Traversal again does not mean 0 Value , Get the number of rows and the number of columns and values 
        for (int i = 0; i < array.length; i++) {
    
            for (int j = 0; j < array[i].length; j++) {
    
                if(array[i][j]!=0){
    
                    nub++;
                    array02[nub][0]=i;
                    array02[nub][1]=j;
                    array02[nub][2]=array[i][j];
                }
            }
        }
        for(int[] ax:array02){
    
            for (int xa:ax){
    
                System.out.print(xa+"\t");
            }System.out.println();
        }
        System.out.println("=============================");
        //  Restore   The first value of the first row of the sparse array is the row of the original array , The second value in the first row is the column of the original array , The third value in the first row is the value of the original array 
        int[][] array03 = new int[array02[0][0]][array02[0][1]];
        for (int i = 1; i < array02.length; i++) {
    
            for (int j = 0; j < array02[j].length; j++) {
    
                array03[array02[i][0]][array02[i][1]]=array02[i][2];
            }
        }
        System.out.println("========================================");
        for (int i = 0; i < array03.length; i++) {
    
            for (int j = 0; j < array03.length; j++) {
    
                System.out.print(array03[i][j]+"\t");
            }
            System.out.println();
        }

    }
}