数据结构-稀疏数组

1、什么是稀疏数组？

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

2、稀疏数组的存储流程

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

3、代码实现

以上面案例作为代码实现的基础:

 public static void main(String[] args) {

        /*
         稀疏数组的存储：
         1.定义原始数组
         2.统计原始数组行列
         3.创建稀疏数组
         4.遍历原始数组，将值存储到稀疏数组

         稀疏数组的还原：
         1.获取稀疏数组中原数组的行列
         2.创建原始数组
         3.遍历稀疏数组进行还原
         */

        int[][] sourceArray = {
                {0,0,0,22,0,0,15},
                {0,11,0,0,0,17,0},
                {0,0,0,-6,0,0,0},
                {0,0,0,0,0,39,0},
                {91,0,0,0,0,0,0},
                {0,0,28,0,0,0,0}
        };

        // 稀疏数组的存储
        int[] colAndRow = getSourceArrayColAndRow(sourceArray);

        int[][] sparseArray = createArray(colAndRow[2]+1, 3);

        setSparseArray(colAndRow,sourceArray,sparseArray);

        printArray(sparseArray);

        // 系数数组的还原
        int[][] originalArray = createArray(sparseArray[0][0], sparseArray[0][1]);

        setSourceArray(sparseArray, originalArray);

        printArray(originalArray);
    }

    private static void setSourceArray(int[][] sparseArray, int[][] originalArray) {
        for (int i = 1; i < sparseArray.length; i++) {
            originalArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }
    }

    private static void printArray(int[][] sparseArray) {
        for(int i = 0; i < sparseArray.length; i++) {
            System.out.println(Arrays.toString(sparseArray[i]));
        }
        System.out.println("==================>");
    }

    private static void setSparseArray(int[] colAndRow, int[][] sourceArray, int[][] sparseArray) {
        sparseArray[0] = new int[]{colAndRow[0],colAndRow[1],colAndRow[2]};
        int index = 1;
        for(int i = 0; i < sourceArray.length; i++){
            for(int j = 0; j < sourceArray[0].length; j++){
                if(sourceArray[i][j] != 0){
                    sparseArray[index++] = new int[]{i, j, sourceArray[i][j]};
                }
            }
        }
    }

    private static int[][] createArray(int col, int row) {
        return new int[col][row];
    }

    private static int[] getSourceArrayColAndRow(int[][] sourceArray) {
        int n = 0;
        for(int i = 0; i < sourceArray.length; i++){
            for(int j = 0; j < sourceArray[0].length; j++){
                if(sourceArray[i][j] != 0){
                    n++;
                }
            }
        }
        return new int[]{sourceArray.length, sourceArray[0].length, n};
    }

4、运行结果