1. 稀疏数组

先看一个实际的需求

五子棋程序中，有存盘退出和续上盘的功能。

分析问题:

因为该二维数组的很多值是默认值 0, 因此记录了很多没有意义的数据.->稀疏数组。

1.1 稀疏数组介绍

当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。 稀疏数组也是一个二维数组，行 取决于有效值的个数+1，列 固定为 3

把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模。

稀疏数组的处理方法是：

• 记录数组一共有几行（i）几列（j），有多少个不同的值（count）。
• 将 i 存到稀疏数组[0][0]的位置
• 将 j 存到稀疏数组[0][1]的位置
• 将 count 存到稀疏数组[0][2]的位置
• 将各个有效值的行列存到稀疏数组下一行，例如[1][0]=行，[1][1]=列，[1][2]=具体值

示意图

1.2 转换思路

二维数组转稀疏数组的思路：

• 遍历原始的二维数组，得到有效数据的个数 sum
• 根据 sum 就可以创建稀疏数组 sparseArr int[sum+1][3]
• 将二维数组的有效数据数据存入到稀疏数组

稀疏数组转原始的二维数组的思路：

1.先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的 chessArr2 =int[5][6]

2.在读取稀疏数组后几行的数据，并赋给原始的二维数组即可

1.3 代码实现

package com.luffy.sparseArray;

import java.util.Arrays;

/**
 * @author dreamLuffe
 * @data 2023/5/11 11:40
 */
@SuppressWarnings("all")
        public class SparseArray {

    public static void main(String[] args) {
        //创建一个原始的而为数组11*11
        //0: 标识没有棋子，1标识黑子 2标识蓝子
        int chessArr1[][] = new int[11][11];
        chessArr1[1][2] = 1;
        chessArr1[2][3] = 2;
        //输出原始的二维数组
        System.out.println("原始的二维数组");
        // 打印
        for (int[] row : chessArr1) {
            System.out.println(Arrays.toString(row));
        }
        //转换成稀疏数组
        int[][] sparseArray = toSparseArray(chessArr1);

        //输出稀疏数组的形式
        System.out.println("得到稀疏数组为～～～");
        // 打印
        for (int[] row : sparseArray) {
            System.out.println(Arrays.toString(row));
        }

        //将稀疏数组 ---> 恢复成原始二维数组
        int[][] orginalArray = toOrginalArray(sparseArray);

        //输出稀疏数组的形式
        System.out.println("恢复后的二维数组为");
        // 打印
        for (int[] row : orginalArray) {
            System.out.println(Arrays.toString(row));
        }


    }

    /**
     *  将稀疏数组转换成原始数组
     * @param sparseArray 稀疏数组
     * @return 原始二维数组
     */
    private static int[][] toOrginalArray(int[][] sparseArray) {
        if(sparseArray == null || sparseArray.length == 0){
            throw new IllegalArgumentException("参数异常");
        }
        int[][] orginalArray = new int[sparseArray[0][0]][sparseArray[0][1]];
            for (int i = 1; i < sparseArray.length; i++) {
                orginalArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
            }
        return orginalArray;
    }

    /**
     * 将原始二维数组转换为稀疏数组
     *
     * @param orginalArray 原始二维数组
     * @return 转换后的稀疏数组
     */
    public static int[][] toSparseArray(int[][] orginalArray) {
        if (orginalArray == null || orginalArray.length == 0) {
            throw new IllegalArgumentException("参数异常");
        }
        //遍历数组得到非零总数
        int sum = 0;
        for (int[] row : orginalArray) {
            for (int item : row) {
                if (item != 0) {
                    sum++;
                }
            }
        }
        //创建一个sum+1行 3列的数组(稀疏数组)
        int[][] sparseArray = new int[sum + 1][3];
        //稀疏数组的行
        sparseArray[0][0] = orginalArray.length;
        //稀疏数组的列
        sparseArray[0][1] = orginalArray[0].length;
        //数组中有多少个非零值
        sparseArray[0][2] = sum;

        //遍历二维数组将非0 存放在sparsearr中
        int count = 1;
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (orginalArray[i][j] != 0) {
                    sparseArray[count][0] = i;
                    sparseArray[count][1] = j;
                    sparseArray[count][2] = orginalArray[i][j];
                    count++;
                }
            }
        }
        return sparseArray;
    }
}