How to convert original array to sparse array in java

1. What is it?

For example, if there is an 11 * 11 backgammon board, and we want to use a program to simulate it, it must be a two-dimensional array. Then use 1 to represent black stones and 2 to represent white stones. If there is only one black stone and one white stone on the chessboard, then there is only one 1 and one 2 in this two-dimensional array, and the others are meaningless 0s that do not represent any chess pieces, as follows:

0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
……

When most of the elements in an array are 0, or have the same value, you can use a sparse array to save the array. Why do this? Because it saves space.

2. How to use?

• Record how many rows and columns the original array has and how many different values ​​it has

• Put the rows and columns of elements with different values and values ​​are recorded in a small-scale array, this small-scale array is called a sparse array

3. Case:

The current situation is as follows The original array of 6 * 7:

0   0   0   22   0   0   15
0   11  0   0    0   17   0
0   0   0  -6    0   0    0
0   0   0   0    0   39   0
91  0   0   0    0   0    0
0   0   28  0    0   0    0

First, the first row and the first column of the sparse array are to record how many rows the element array has. The first row and the second column are to record how many columns the original array is. The first row and the first column are The three columns record how many different values ​​the original array has (except 0). So one row of the sparse array should be:

行    列    值
6     7     8

Starting from the second row of the sparse array, each row records the row, column, and value size of the non-0 value in the original array. For example, if the second line is to record the row, column, and value of 22 in the original array, then the second line of the sparse array is:

行    列    值
0     3     22

Then use this method to record 15, 11, 17, -6, 39, 91 , 28 related information, so the sparse array finally converted from the original array is:

行    列    值
6     7     8
0     3     22
0     6     15
1     1     11
1     5     17
2     3     -6
3     5     39
4     0     91
5     2     28

This turns a 6 * 7 array into a 9 * 3 array, achieving the compression effect .

4. Ideas for converting original arrays and sparse arrays:

Convert original arrays to sparse arrays:

• Traverse two dimensions The array gets the number of valid arrays count;

• You can create a sparse array based on count int[count 1][3];

• Save the valid array into a sparse array

Convert sparse array to original Array:

• Read the first row of the sparse array. Based on the first row of the array, you can know how many rows and columns the original array has, and then create the original array;

• Read the array of several rows after the sparse array and assign it to the original array

##5. Code practice:

public class SparseArray {
    public static void main(String[] args){
        // 创建一个 11 * 11的原始数组
        int[][] arr1 = new int[11][11];
        arr1[1][2] = 1;
        arr1[2][3] = 2;

        // 原始数组转稀疏数组
        // 1. 遍历，得到非0数据的个数以及所在的行列
        int count = 0;
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < arr1.length; i++) {
            for (int j = 0; j < arr1[i].length; j++) {
                if (arr1[i][j] != 0){
                    count ++;
                    map.put(i+ "," + j, arr1[i][j]);
                }
            }
        }
        // 2. 创建稀疏数组
        int[][] sparseArr = new int[count + 1][3];
        sparseArr[0][0] = arr1.length;
        sparseArr[0][1] = arr1[0].length;
        sparseArr[0][2] = count;
        // 3. 给稀疏数组赋值
        int row = 1;
        for (String key : map.keySet()){
            String[] ij = key.split(",");
            int i = Integer.parseInt(ij[0]);
            int j = Integer.parseInt(ij[1]);
            sparseArr[row][0] = i;
            sparseArr[row][1] = j;
            sparseArr[row][2] = map.get(key);
            row ++;
        }
        // 4. 遍历稀疏数组
        for (int i = 0; i < sparseArr.length; i++) {
            for (int j = 0; j < sparseArr[i].length; j++) {
                System.out.print(sparseArr[i][j] + "   ");
            }
            System.out.println("\r\n");
        }

        // 稀疏数组恢复原始数组
        // 1. 根据第一行第一列第二列创建出原始数组
        int i = sparseArr[0][0];
        int j = sparseArr[0][1];
        int[][] arr2 = new int[i][j];
        // 2. 给原始数组赋值
        for (int k = 1; k < sparseArr.length; k++) {
            int x = sparseArr[k][0];
            int y = sparseArr[k][1];
            int val = sparseArr[k][2];
            arr2[x][y] = val;
        }
        // 3. 遍历转换的数组
        for (int a = 0; a < arr2.length; a++) {
            for (int b = 0; b < arr2[a].length; b++) {
                System.out.print(arr2[a][b] + "   ");
            }
            System.out.println("\r\n");
        }
    }
}

The above code realizes the mutual conversion between original array and sparse array. Flexible use of sparse array can save running memory and improve program performance.

The above is the detailed content of How to convert original array to sparse array in java. For more information, please follow other related articles on the PHP Chinese website!