稀疏数组

实际问题：

1）基本介绍

当一个数组中大部分元素都是0、或大部分都是相同的元素时，可以使用稀疏数组来保存此数组

处理方法：

• 第一行记录数组一共有几行几列，有多少个不同的值

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

2）应用实例

代码实现：

package DataStructures.SparseArray;

import java.io.Serializable;

/**
 * @author Loe.
 * @project DataStructures&Algorithms
 * @date 2023/4/23
 * @ClassInfo
 */
public class Main {

    public static void main(String[] args) {

        //初始化原始数组,并赋值
        int[][] maps = new int[11][11];
        maps[1][2] = 1;
        maps[2][3] = 2;

        System.out.println("原始数组");
        printArray(maps);

        //进行稀疏操作
        SparsArray sparsArray = new SparsArray(0, maps);
        System.out.println();
        //打印稀疏后的数组
        System.out.println("稀疏操作后的数组");
        printArray(sparsArray.getSparsArray());
        System.out.println();

        //从稀疏数组恢复到原始数组
        System.out.println("恢复后的数组");
        int[][] sourceArray = sparsArray.reduction();
        printArray(sourceArray);

        //将此稀疏数组对象持久化
    }

    public static void printArray(int[][] maps) {
        for (int i = 0; i < maps.length; i++) {
            for (int j = 0; j < maps[i].length; j++) {
                System.out.print(maps[i][j] + " ");
            }
            System.out.println();
        }
    }
}

//实现稀疏数组
class SparsArray implements Serializable {
    //默认值
    public int defaultVal;

    //数组相关
    public int row;
    public int col = 3;

    //有效的数据
    int useAbleDataCount;

    //稀疏数组
    public int[][] sparsArray;

    //初始化数组
    public SparsArray(int defaultVal, int[][] targetArr) {
        this.defaultVal = defaultVal;
        //获取可用的数据数量
        this.useAbleDataCount = countDataNums(targetArr);
        //初始化对象稀疏数组
        this.sparsArray = new int[useAbleDataCount + 1][3];
        //稀疏数组赋值
        spars(targetArr);
    }

    //遍历数组,统计有效的数据
    public int countDataNums(int[][] maps) {
        int count = 0;
        for (int i = 0; i < maps.length; i++) {
            for (int j = 0; j < maps[i].length; j++) {
                if (!(maps[i][j] == defaultVal)) {
                    count++;
                }
            }
        }
        return count;
    }

    public void spars(int[][] targetArr) {
        //当前稀疏数组的行
        int sparsRow = 1;

        //记录原始数组的信息
        this.sparsArray[0][0] = targetArr.length;
        this.sparsArray[0][1] = targetArr[0].length;
        this.sparsArray[0][2] = this.useAbleDataCount;


        for (int i = 0; i < targetArr.length; i++) {
            for (int j = 0; j < targetArr[i].length; j++) {
                if (!(targetArr[i][j] == defaultVal)) {
                    sparsArray[sparsRow][0] = i;
                    sparsArray[sparsRow][1] = j;
                    sparsArray[sparsRow][2] = targetArr[i][j];
                    sparsRow++;
                }
            }
        }
    }

    //从稀疏数组还原到原来的数组
    public int[][] reduction() {
        //创建恢复的数组
        int[][] reductionArr = new int[sparsArray[0][0]][sparsArray[0][1]];
        //稀疏数组当前行
        int row = 1;

        //遍历恢复的数组,并恢复对应值
        for (int i = 0; i < reductionArr.length; i++) {
            for (int j = 0; j < reductionArr[i].length; j++) {
                //如果已经将有效数据全部恢复
                if (row <= useAbleDataCount) {
                    System.out.println(row);
                    //还没有将数据全部恢复,继续判断
                    if (i == sparsArray[row][0] && j == sparsArray[row][1]){
                        reductionArr[i][j] = sparsArray[row][2];
                        row++;
                    }
                   
                } else {
                    reductionArr[i][j] = this.defaultVal;
                }
            }
        }

        return reductionArr;
    }


    public int[][] getSparsArray() {
        return sparsArray;
    }
}