Java稀疏数组

当一个数组中大部分元素为0，或者为同一值的数组时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方式是:记录数组一共有几行几列，有多少个不同值；把具有不同值的元素和行列及值记录在一个小规模的数组中，从而缩小程序的规模

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

如图，把一个6X7的二维数组变为了一个9X3的稀疏数组。其中

• 第一行保存的是原二维数组的行、列以及非0值的个数
• 第二到九行保存的是每个非0值所在的位置及其数值

二维数组转稀疏数组

• 遍历二维数组，得到二维数组中有效值的个数sum，创建稀疏数组，有sum+1行，3列（固定）
• 将二维数组中的有效值存入稀疏数组中

稀疏数组转二维数组

先读取稀疏数组的第一行（保存二维数组的行列信息），还原二维数组
读取稀疏数组的其他行，将值赋给二维数组的对应位置上的数

public class SparseArray {
    public static void main(String[] args) {
        // 先定义一个二维数组
        int[][] arr = new int[11][11];

        // 随机在二维数组中插入几个非零的数
        arr[0][3] = 31;
        arr[2][6] = 9;
        arr[5][8] = 65;
        arr[6][9] = 96;
        arr[4][1] = -1;
        arr[8][0] = 2;
        arr[10][1] = 101;

        // 循环遍历打印
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j]+ " ");
            }
            System.out.println();
        }

        // 获取二维数组中非零的个数
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                if (arr[i][j]!=0){
                    sum++;
                }
            }
        }
        System.out.println(sum);    // 打印得到7个非零的数
        
        int sparse [][] = new int[sum+1][3];
        sparse[0][0] = arr.length;
        sparse[0][1] = arr[0].length;
        sparse[0][2] = sum;
        // 定义一个count，来控制行号，从第二行开始，因为他的列索引的值已经固定好了。
        int count = 1;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                if (arr[i][j]!=0){
                    sparse[count][0] =i;
                    sparse[count][1] =j;
                    sparse[count][2] = arr[i][j];
                    count ++;
                }
            }
        }

        for (int i = 0; i < sparse.length; i++) {
            for (int j = 0; j < sparse[i].length; j++) {
                System.out.print(sparse[i][j]+" ");
            }
            System.out.println("");
        }
		
        int[][] newArr = new int[sparse[0][0]][sparse[0][1]];

        // 遍历稀疏数组，将不为零的坐标还原到二维数组上
        for (int i = 1; i < sparse.length ; i++) {
            newArr[sparse[i][0]][sparse[i][1]] = sparse[i][2];
        }

		//  遍历打印
        for (int i = 0; i < newArr.length; i++) {
            for (int j = 0; j < newArr[i].length; j++) {
                System.out.print(newArr[i][j]+" ");
            }
            System.out.println("");
        }
    }
}

原二维数组
0 0 0 31 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 9 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 0 0 0 0 65 0 0 
0 0 0 0 0 0 0 0 0 96 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 0 0 0 0 0 0 0 0 
0 101 0 0 0 0 0 0 0 0 0 
转为的稀疏数组
7
11 11 7 
0 3 31 
2 6 9 
4 1 -1 
5 8 65 
6 9 96 
8 0 2 
10 1 101 
稀疏数组转化得到的二维数组
0 0 0 31 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 9 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 0 0 0 0 65 0 0 
0 0 0 0 0 0 0 0 0 96 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 0 0 0 0 0 0 0 0 
0 101 0 0 0 0 0 0 0 0 0