数据结构 - 稀疏数组

2 稀疏数组（SparseArray）

--（1）什么是稀疏数组？
    稀疏数组：当一个二维数组中很多值是默认值0，因此记录了很多没有意义的数据。使用稀疏数组可以节省空间，只保存元素在二维数组中的位置和所对应的值。
    稀疏数组的样式为：
    		row  		   col  			 val
    0	原数组行数		 原数组列数			不为0元素个数
    1	不为0的值所在行   不为0的值所在列		  元素的值
    。。。。

--（2）稀疏数组的使用场景？
    当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
    
--（3）稀疏数组的处理方法？
    ①记录数组一共有几行几列，有多少个不同的值。
    ②把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模。

二维数组<–>稀疏数组

public class SparseArrayTest2 {
    public static void main(String[] args) {
        //1初始化二维数组
        int[][] arr = new int[11][11];
        arr[1][2] = 1;//1 表示黑子
        arr[2][4] = 2;
        arr[4][5] = 2;//2 表示蓝子
        //显示原有的二维数组
        System.out.println("----------------原始的二维数组-----------------");
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + "\t");
            }
            System.out.println();
        }
        //2创建稀疏数组
        //遍历原始二维数组计算一共有几个不为0的数
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                if (arr[i][j] != 0){
                    count++;
                }
            }
        }	
        //创建稀疏数组
        int[][] sparseArray = new int[count + 1][3];
        //给二维数组的第一行赋值
        sparseArray[0][0] = arr.length;
        sparseArray[0][1] = arr[0].length;
        sparseArray[0][2] = count;
        //遍历原始二维数组，给稀疏数组赋值
        int num = 0;//定位稀疏数组的行
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                if (arr[i][j] != 0){
                    num++;
                    sparseArray[num][0] = i;
                    sparseArray[num][1] = j;
                    sparseArray[num][2] = arr[i][j];
                }
            }
        }
        //展示稀疏数组
        System.out.println("----------------稀疏数组-----------------");
        for (int i = 0; i < sparseArray.length; i++) {
            for (int j = 0; j < sparseArray[i].length; j++) {
                System.out.print(sparseArray[i][j]+"\t");
            }
            System.out.println();
        }
        //3 将生成的稀疏数组再转换成二维数组
        //定义一个新的二维数组
        int[][] arrNew = new int[sparseArray[0][0]][sparseArray[0][1]];
        //给新的二维数组赋值;遍历二维数组
        for (int i = 1; i <= sparseArray[0][2]; i++) {
            arrNew[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }
        //展示新生成的二维数组
        for (int i = 0; i < arrNew.length; i++) {
            for (int j = 0; j < arrNew[i].length; j++) {
                System.out.print(arr[i][j] + "\t");
            }
            System.out.println();
        }
    }
}