稀疏矩阵算算法

个人理解:
将一个矩阵二维数组抽取出有用的点,然后记录起来

使用场景:
棋盘

0 表示未走棋子
1 表示黑子
2 表示白子

抽取前的棋盘数组为:

0	0	0	0	0	0	0	0	0	0	0	
0	0	1	0	0	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	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0
复制代码

抽取后的稀疏数组:

解读抽取后的稀疏数组:

[0][0] 位置为二维数组行
[0][1] 位置为二维数组列
[0][2] 位置为二维数组有效点数(1 和 2 )总数
[1][0] 为第一颗棋子行坐标
[1][1] 为第一颗棋子列坐标
[1][2] 为第一颗棋子的值(1 表示黑子)

依次类推,记录棋盘所有棋子的坐标以及值

辅助图:

总结: 稀疏算法也是一个二维数组,最终行的个数为总数+1,列为 3

    //countTemp + 1为行 (countTemp为当前棋盘中有效数(!=0 的数))
    //3为列
 int sparseArray[][] = new int[countTemp + 1][3];
复制代码

辅助图:

创建二维数组

这里以 11 * 11 的二维数组为例

    //行
    public static int mRow = 11;
    //列
    public static int mColumn = 11;

  //TODO 创建原始二维数组 数据
        int chessArr1[][] = new int[mRow][mColumn];

        //给黑子 白子赋值
        chessArr1[1][2] = 1;//1为黑子
        chessArr1[2][3] = 2;//2 为白子
//        chessArr1[5][2] = 1;


        System.out.println("原始的二维数组为:");
        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1[i].length; j++) {
                System.out.printf("%d\t", chessArr1[i][j]);
            }
            System.out.println();
        }
复制代码

运行结果为:

原始的二维数组为:
0	0	0	0	0	0	0	0	0	0	0	
0	0	1	0	0	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	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
复制代码

二维数组转稀疏数组

先记录棋盘中的所有棋子(!=0 的数)

//先得到棋盘中的所有棋子 !=0 的数

 int countTemp = 0;
        //遍历行
        for (int i = 0; i < mRow; i++) {
            //遍历列
            for (int j = 0; j < mColumn; j++) {
                if (chessArr1[i][j] != 0) {
                    countTemp++;
                }
            }
        }
        System.out.println("非 0 个数有 " + countTemp + "个");
复制代码

创建稀疏数组:

给第一行赋值:

 int sparseArray[][] = new int[countTemp + 1][3];

        //TODO 给稀疏数组第一行赋值
        //行
        sparseArray[0][0] = mRow;
        //列
        sparseArray[0][1] = mColumn;
        //总数
        sparseArray[0][2] = countTemp;
复制代码

循环二维数组,将!=0 的值赋值给稀疏数组并打印:

//用来记录是第几个非 0 数据
        int countTemp2 = 0;
        //遍历二维数组,将非 0 的数据放到sparseArray[][]中
        for (int i = 0; i < mRow; i++) {
            //遍历列
            for (int j = 0; j < mColumn; j++) {
                if (chessArr1[i][j] != 0) {
                    countTemp2++;
                    sparseArray[countTemp2][0] = i;//i = 行
                    sparseArray[countTemp2][1] = j;//j = 列
                    sparseArray[countTemp2][2] = chessArr1[i][j];//chessArr1[i][j] = 具体的值
                }
            }
        }

        //TODO 输出稀疏数组
        System.out.println("稀疏数据为:");
        //遍历行
        for (int i = 0; i < sparseArray.length; i++) {
            //遍历列
            for (int j = 0; j < sparseArray[i].length; j++) {
                System.out.printf("%d\t", sparseArray[i][j]);
            }
            System.out.println();
        }
复制代码

稀疏数组运行结果为:

稀疏数据为:
11	11	2	
1	2	1	
2	3	2	
复制代码

稀疏数组转二维数组

创建二维数组

行为稀疏数组 [0][0] 位置
列为稀疏数组 [0][1] 位置
循环次数为二维数组长度

int array[][] = new int[sparseArray[0][0]][sparseArray[0][1]];

        System.out.println("sparseArray.length" + sparseArray.length);
        //第一行为原始数组的 行 列 个数,所以从第一行开始遍历
        for (int i = 1; i < sparseArray.length; i++) {
            /**
             * 只循环有值的,因为 int array[][] 默认其他数值为 0
             * sparseArray[i][0] = 行
             * sparseArray[i][1] = 列
             * sparseArray[i][2] = 值
             */
            array[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }

        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                System.out.printf("%d\t", array[i][j]);
            }
            System.out.println();
        }
复制代码

运行结果为:

sparseArray.length3
0	0	0	0	0	0	0	0	0	0	0	
0	0	1	0	0	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	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
复制代码