谈一下稀疏数组

对于一个初窥数据结构的人来说，稀疏数组确实可以很好的帮助你锻炼思维。

但自从第三次科技革命后，人们都一直在做着用空间去换取时间的损事，而以时间换空间的稀疏数组，倒也跟北大考古专业有些心心相惜。

稀疏数组的基本介绍：

当一个数组中大部分元素为0，或者为同一个值时，可以使用稀疏数组来保存该数组

如何创建一个稀疏数组：

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

（小规模数组便是稀疏数组）

应用场景：

 

像在编写的五子棋程序中，有存盘退出和续上局功能

在存盘的时候，将黑白子以及空位都分别以1,2,0存放在一个二维数组中，当棋盘上空位比较多的时候，大量的0（重复数据）会占用较高的空间，为了节省空间，便有了稀疏数组。

如上图，将一个棋盘映射成为一个二维数组，在数组中，有大量重复的数据.

这时，我们可以将棋盘的行、列以及非0的数据抽取出来，分别作为稀疏数组的 SparseArray[0][0]、SparseArray[0][1]、SparseArray[0][2]。

将非重复数据的行、列、值依次存储在稀疏数组中，便有了一个较小规模的数组，以节省空间。

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

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

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

• 先读取稀疏数组的第一行，根据第一行创建原始数组chessArr2 = int[11]；
• 在读取稀疏数组后几行的数据，并赋给原始的二维数组。

package com.perwrj.sparsearray;

public class SparseArray {

    public static void main(String[] args) {
        /*
         * 原始数组的创建与遍历
         */
        System.out.println("原始的二维数组");
        int  chessArr [][] = new int[11][11];
        chessArr [1][2] = 1;
        chessArr [2][3] = 2;
        for (int[] is : chessArr) {
            for (int is2 : is) {
                System.out.print("\t" + is2);
            }
            System.out.println("\n");
        }
        
        /*
         * 将原始数组转换为稀疏数组
         */
//        获取原始数组中不为零值的个数
        int sum = 0;
        for (int i = 0; i < chessArr.length; i++) {
            for (int j = 0; j < chessArr[i].length; j++) {
                if (chessArr[i][j] != 0) {
                    sum ++;
                }
            }
        }
//        给稀疏数组第一行赋值，分别为原始数组的行，列，不为零值个数
        int sparseArr[][] = new int [sum + 1][3];
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = sum;
        
//        遍历原始数组，为稀疏数组其他赋值（原始数组中非零的数）
        int count = 0;
        for (int i = 0; i < chessArr.length; i++) {
            for (int j = 0; j < chessArr[i].length; j++) {
                if (chessArr[i][j] != 0) {
                    count++;
                    sparseArr[count][0]= i;
                    sparseArr[count][1]= j;
                    sparseArr[count][2]= chessArr[i][j];
                }
            }
        }
        
//        打印遍历稀疏数组
        System.out.println("稀疏数组");
        for (int[] is : sparseArr) {
            for (int is2 : is) {
                System.out.print("\t" + is2);
            }
            System.out.println("\n");
        }
        
        /*
         * 稀疏数组转换为原始数组
         */
//        用稀疏数组第一行创建原始数组
        int chessArr2 [][] = new int[sparseArr[0][0]][sparseArr[0][1]];
        
//        遍历赋值原始数组
        for (int i = 1; i < sparseArr.length; i++) {
                chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        
//        遍历还原后的数组
        System.out.println("还原后的二维数组");
        for (int[] is : chessArr2) {
            for (int is2 : is) {
                System.out.print("\t" + is2);
            }
            System.out.println("\n");
        }
    }

}