『数据结构与算法』稀疏数组

微信搜索:码农StayUp
主页地址:https://gozhuyinglong.github.io
源码分享:https://github.com/gozhuyinglong/blog-demos

五子棋游戏的存取需求

在介绍稀疏数组前我们先来引入一个需求,下面是一个五子棋的棋盘(15 * 15),玩到中途时想要保存离开,希望下次打开还可以继续玩。我们怎么实现呢?
『数据结构与算法』稀疏数组
从对棋盘的观察来看,我们可以使用int型的二维数组进行存储,将未落子的地方存储0,白子存储1,黑子存储2,那么我们的数组可能是这样的:
『数据结构与算法』稀疏数组

可以看出,使用二维数组是能解决这个需求的。但我们也发现了一个问题,上面存储相同数值的0比较多,这对空间造成了浪费,有没有另外一种存储方式呢?答案是可以使用稀疏数组,下面我们来看稀疏数组是怎么实现的!

稀疏数组(Sparse Array)

当一个数组中大部分元素是0,或者是一个相同的值时,可以使用稀疏数组来保存该数组。

稀疏数组的处理方式是:

  1. 记录数组一共有几行几列,以及不同值的数量
  2. 把具有不同值元素的行列及其值记录在一个小规模的数组中,从而缩小数据的规模。

那我们把上面二维数组转为稀疏数组存储,看是什么样子的。

『数据结构与算法』稀疏数组
第一行(即:0行)比较特殊,row存储总行数,col存储总列数,value存储非零(不同值)元素的数量;
其他行结构相同,每一行存储一条非零元素信息,row存储元素所在行,col存储元素所在列,value存储元素的值。

代码实现

我们使用代码来实现二维数组与稀疏数组的相互转换,下面是具体的实现!

public class SparseArrayDemo {

    public static void main(String[] args) {
        System.out.println("-----------------------普通数组");
        int[][] initialArray = initArray();
        printArray(initialArray);
        System.out.println("-----------------------普通数组 --> 稀疏数组");
        int[][] sparseArray = arrayConvertSparseArray(initialArray);
        printArray(sparseArray);
        System.out.println("-----------------------稀疏数组 --> 普通数组");
        int[][] array = sparseArrayConvertArray(sparseArray);
        printArray(array);
    }

    /**
     * 初始化五子棋数组
     *
     * @return
     */
    static int[][] initArray() {
        // 0为空,1为白子,2为黑子
        int[][] array = new int[15][15];
        array[3][11] = 1;
        array[4][10] = 2;
        array[5][9] = 2;
        array[6][8] = 2;
        array[6][7] = 1;
        array[7][8] = 1;
        array[7][7] = 2;
        array[8][6] = 1;
        return array;
    }

    /**
     * 打印二维数组
     *
     * @param array
     */
    static void printArray(int[][] array) {
        for (int[] row : array) {
            for (int data : row) {
                System.out.printf("%s\t", data);
            }
            System.out.println();
        }
    }

    /**
     * 统计非零值数量
     *
     * @param array
     * @return
     */
    static int valueCount(int[][] array) {
        int count = 0;
        for (int[] row : array) {
            for (int data : row) {
                if (data != 0) {
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * 普通数组转为稀疏数组
     *
     * @param array
     * @return
     */
    static int[][] arrayConvertSparseArray(int[][] array) {
        int rowNum = array.length;
        int colNum = array[0].length;
        int valueNum = valueCount(array);

        int[][] sparseArray = new int[valueNum + 1][3];
        sparseArray[0][0] = rowNum;
        sparseArray[0][1] = colNum;
        sparseArray[0][2] = valueNum;

        int rowCount = 1;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                int value = array[i][j];
                if (value != 0) {
                    sparseArray[rowCount][0] = i;
                    sparseArray[rowCount][1] = j;
                    sparseArray[rowCount][2] = value;
                    rowCount++;
                }
            }
        }
        return sparseArray;
    }

    /**
     * 稀疏数组转为普通数组
     *
     * @param sparseArray
     * @return
     */
    static int[][] sparseArrayConvertArray(int[][] sparseArray) {
        int rowNum = sparseArray[0][0];
        int colNum = sparseArray[0][1];
        int valueNum = sparseArray[0][2];

        int[][] array = new int[rowNum][colNum];

        for (int i = 1; i < valueNum + 1; i++) {
            int row = sparseArray[i][0];
            int col = sparseArray[i][1];
            int value = sparseArray[i][2];
            array[row][col] = value;
        }

        return array;
    }
}

输出结果:

-----------------------普通数组
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	0	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	2	0	0	0	0	0	
0	0	0	0	0	0	0	1	2	0	0	0	0	0	0	
0	0	0	0	0	0	0	2	1	0	0	0	0	0	0	
0	0	0	0	0	0	1	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	
-----------------------普通数组 --> 稀疏数组
15	15	8	
3	11	1	
4	10	2	
5	9	2	
6	7	1	
6	8	2	
7	7	2	
7	8	1	
8	6	1	
-----------------------稀疏数组 --> 普通数组
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	0	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	2	0	0	0	0	0	
0	0	0	0	0	0	0	1	2	0	0	0	0	0	0	
0	0	0	0	0	0	0	2	1	0	0	0	0	0	0	
0	0	0	0	0	0	1	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	

推荐阅读

作者:码农StayUp
出处:https://mp.weixin.qq.com/s/YYemaomm10HiKs9MoKHKIw
版权:本文采用「署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)」知识共享许可协议进行许可。

上一篇:HashMap提升版SparseArray,进阶版ArrayMap


下一篇:稀疏sparsearray数组