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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了『数据结构与算法』稀疏数组，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4779字，纯文字阅读大概需要7分钟。

内容图文

微信搜索：码农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	

推荐阅读

• 《 数组 》
• 《 稀疏数组 》
• 《 链表（单链表、双链表、环形链表） 》
• 《 栈 》
• 《 队列 》
• 《 树 》
• 《 二叉树 》
• 《 二叉查找树（BST） 》
• 《 AVL树（平衡二叉树） 》
• 《 B树 》
• 《 散列表（哈希表） 》

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

内容总结

以上是互联网集市为您收集整理的『数据结构与算法』稀疏数组全部内容，希望文章能够帮你解决『数据结构与算法』稀疏数组所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---