环球今热点：稀疏数组

(资料图片仅供参考)

实际问题：

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

处理方法：

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

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

代码实现：

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;    }}

标签：