稀疏数组

package com._1_Java数据结构_尚硅谷._1稀疏数组;

/** * @author: 97942 * @date: 2021/9/20 10:24 * @description:稀疏数组实现 */
public class 稀疏数组实现
{
    public static void main(String[] args) {
        // 0 创建稀疏矩阵
        int arr[][] = new int[6][7];
        arr[0][3] = 22;
        arr[0][6] = 15;
        arr[1][1] = 11;
        arr[1][5] = 17;
        arr[2][3] = -6;
        arr[3][5] = 39;
        arr[4][0] = 91;
        arr[5][2] = 28;
        System.out.println("\n0 原始矩阵：");
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.printf("\t%d\t",arr[i][j]);
            }
            System.out.println();   // 每一行后面换行
        }

        // 1 生成稀疏矩阵
        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++;
            }
        }
        int[][] sparsearr = new int[sum+1][3];  //稀疏数组的行数是 原始数组非零个数 + 1
        sparsearr[0][0] = arr.length;                 //原始数组的行数
        sparsearr[0][1] = arr[0].length;              //原始数组的列数
        sparsearr[0][2] = sum;                        //原始数组非零个数

        int count= 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                if (arr[i][j] !=0)
                {
                    count++;
                    sparsearr[count][0] = i;
                    sparsearr[count][1] = j;
                    sparsearr[count][2] = arr[i][j];
                }

            }
        }

        System.out.println("\n1 稀疏数组：");
        for (int i = 0; i < sparsearr.length; i++) {
            for (int j = 0; j < sparsearr[i].length; j++) {
                System.out.printf("\t%d\t",sparsearr[i][j]);
            }
            System.out.println();   // 每一行后面换行
        }

        //2 从稀疏数组恢复原始数组
        int[][] originArr = new int[sparsearr[0][0]][sparsearr[0][1]];
        for (int i = 1; i < sparsearr.length; i++) {
            for (int j = 0; j < sparsearr[0].length; j++) {
                originArr[sparsearr[i][0]][sparsearr[i][1]] = sparsearr[i][2];
            }
        }

        System.out.println("\n2 恢复原始数组：");
        for (int i = 0; i < originArr.length; i++) {
            for (int j = 0; j < originArr[i].length; j++) {
                System.out.printf("\t%d\t",originArr[i][j]);
            }
            System.out.println();   // 每一行后面换行
        }

    }
}