数据结构与算法

1. 稀疏数组（sparsearray）

因为二维数组有很多值默认为0，因此记录了很多没有意义的数据，此时就可以使用稀疏数组来保存数据

稀疏数组的处理方法：

  1）记录一共有几行几列
  2）把具有不通知的元素的行列记录在一个小规模的数组中，从而缩小程序的规模

二维数组转稀疏数组思路：

	1.遍历原始的二维数组，得到有效数据的个数
	2.根据得到的有效个数创建一个稀疏数组
	3.将二位数组的有效数据存入到稀疏数组

稀疏数组转为二维数组的思路：

	1.先读取稀疏数组的第一行，并根据第一行的数据创建二维数组
	2.在读取稀疏数组后几行的数据，并赋给二维数据

代码实现

/**
 * @author Little Boy
 * @title SparseArray
 * @projectName 数据结构与算法
 * @description 稀疏数组
 * @date 2021/8/18 13:26
 */
public class SparseArray {

    /**
      * @auther Little Boy
      * @title main
      * @description 稀疏数组
      * @params [args]
      * @date 2021/8/18 13:27
      */
    public static void main(String[] args) {
        // 创建二维数组
        int[][] arr1 = new int[13][11];
        // 给二维数组赋值
        arr1[1][6] = 78;
        arr1[3][7] = 56;
        arr1[4][6] = 10;
        arr1[3][8] = 170;
        arr1[7][6] = 50;
        arr1[2][4] = 12;
        // 转为稀疏数组
        int[][] sparseArray = arrayToSparseArray(arr1);

        System.out.println("======----------------------------------------------------------======");

        // 将稀疏数组转为二维数组
        sparseArrayToArray(sparseArray);
    }

    /**
      * @auther Little Boy
      * @title arrayToSparseArray
      * @description 二维数组转稀疏数组
      * @params [ints]
      * @date 2021/8/18 13:31
      */
    public static int[][] arrayToSparseArray(int[][] ints){
        // 输出二维数组
        System.out.println("====================原始二维数组====================");
        for(int[] row : ints){
            for (int data : row){
                System.out.print(data + "\t");
            }
            System.out.println();
        }
        // 得到有效个数
        int sum = 0;
        for (int row = 0; row < ints.length;row++){
            for (int col = 0; col < ints[row].length;col++){
                if(ints[row][col] != 0){
                    sum++;
                }
            }
        }

        // 根据得到的有效个数创建稀疏数组
        int[][] sparseArray = new int[sum + 1][3];
        // 记录二维数组的行列和有效数据

        // 用于记录第几行
        int rows = 1;
        sparseArray[0][0] = ints.length;
        sparseArray[0][1] = ints[0].length;
        sparseArray[0][2] = sum;
        // 存入数据
        for (int row = 0; row < ints.length;row++){
            for (int col = 0; col < ints[row].length;col++){
                if(ints[row][col] != 0){
                    sparseArray[rows][0] = row;
                    sparseArray[rows][1] = col;
                    sparseArray[rows][2] = ints[row][col];
                    rows++;
                }
            }
        }
        // 输出稀疏数组
        System.out.println("====================转为稀疏数组====================");
        for(int[] row : sparseArray){
            for (int data : row){
                System.out.print(data + "\t");
            }
            System.out.println();
        }
        return sparseArray;
    }

    /**
      * @auther Little Boy
      * @title sparseArrayToArray
      * @description 稀疏数组转为二维数组
      * @params [sparseArrayInts]
      * @date 2021/8/18 14:20
      */
    public static int[][] sparseArrayToArray(int[][] sparseArrayInts){
        // 输出稀疏数组
        for(int[] row : sparseArrayInts){
            for (int data : row){
                System.out.print(data + "\t");
            }
            System.out.println();
        }

        // 将稀疏数组转为二维数组

        // 创建二维数组
        int rows = 1;
        int[][] arrs = new int[sparseArrayInts[0][0]][sparseArrayInts[0][1]];

        for (int i = 1; i < sparseArrayInts.length; i++) {
            arrs[sparseArrayInts[i][0]][sparseArrayInts[i][1]] = sparseArrayInts[i][2];
        }

        System.out.println("====================输出二维数组==================");
        for(int[] row : arrs){
            for (int data : row){
                System.out.print(data + "\t");
            }
            System.out.println();
        }

        return arrs;
    }

}

输出：

====================原始二维数组====================
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	78	0	0	0	0	
0	0	0	0	12	0	0	0	0	0	0	
0	0	0	0	0	0	0	56	170	0	0	
0	0	0	0	0	0	10	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	50	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
====================转为稀疏数组====================
13	11	6	
1	6	78	
2	4	12	
3	7	56	
3	8	170	
4	6	10	
7	6	50	
======----------------------------------------------------------======
13	11	6	
1	6	78	
2	4	12	
3	7	56	
3	8	170	
4	6	10	
7	6	50	
====================输出二维数组==================
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	78	0	0	0	0	
0	0	0	0	12	0	0	0	0	0	0	
0	0	0	0	0	0	0	56	170	0	0	
0	0	0	0	0	0	10	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	50	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0