稀疏数组 sparse array

概述

在一个数组里有多个同值的单元时，可以用稀疏数组进行压缩，只保留有效数字。也就是说在数据稀少的情况下才有优势。

举个栗子

下图二维数组里，大多数都是0，真正有意义的数字只有5个。存那么多零岂不是浪费空间？

---

因此我们可以根据对应的行列，只存储有效数值。
注意:第一部分存储总行列数和有效值个数，以便于复原时创建数组。

二维转稀数思路

1.遍历二维数组，得到有效值数量sum
2.根据sum创建稀数组，spareArr int[sum+1][列]
3.将有效数值存入稀数组

稀数转二维思路

1.读取第一行数据后创建二维数组
2.继续读取数据，存入二维数组

造轮子！！

我们可以来看一下稀数数组在五子棋的应用

//五子棋游戏
//创建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){
    for(int data : row){
        System.out.printf("%d\t",data);
    }
    System.out.println();
}

//遍历数组得到有效值个数
int sum = 0;
for(int i = 0;i < 11;i++){
    for(int j = 0;j < 11;j++){
        if(chessArr1[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 < 11;i++){
    for(int j = 0;j < 11;j++){
        if(chessArr1[i][j] != 0){
            count++;
            sparseArr[count][0] = i;
            sparseArr[count][1] = j;
            sparseArr[count][2] = chessArr1[i][j];
        }
    }
}

System.out.println("稀疏数组");
for(int i = 0;i<sparseArr.length;i++){
    System.out.printf("%d\t%d\t%d\t\n",sparseArr[i][0],sparseArr[i][1],sparseArr[i][2]);
}

//恢复

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[] row : chessArr1){
    for(int data : row){
        System.out.printf("%d\t",data);
    }
    System.out.println();
}
  

最后输出的效果图是这样的