稀疏数组

普通数组压缩为稀疏数组

代码实现

public class SparseArray {
    public static void main(String[] args) {
        int[][] array = new int[4][5];
        //初始化二维数组
        array[0][2] = 1;
        array[1][1] = 2;
        array[2][3] = 3;
        //记录普通数组中的有效值个数并且遍历普通数组
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j <array[i].length ; j++) {
                if (array[i][j] != 0) {
                    //本例将不为0的数视为有效值
                    count++;
                }
                System.out.print(array[i][j]+" ");
            }
            System.out.println();
        }
        //创建稀疏数组
        int[][] sparesArray = new int[count+1][3];
        sparesArray[0][0] = array.length;
        sparesArray[0][1] = array[0].length;
        sparesArray[0][2] = count;
        int index = 0;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                if (array[i][j] != 0){
                	//将普通数组转化为稀疏数组
                    index++;
                    sparesArray[index][0] = i;
                    sparesArray[index][1] = j;
                    sparesArray[index][2] = array[i][j];
                }
            }
        }
        //遍历稀疏数组
        for (int i = 0; i < sparesArray.length; i++) {
            for (int j = 0; j < sparesArray[i].length; j++) {
                System.out.print(sparesArray[i][j]);
                System.out.print(" ");
            }
            System.out.println();
        }
    }
}

输出结果

将稀疏数组还原为普通数组

代码实现

//还原稀疏数组
        int[][] revertArray = new int[sparesArray[0][0]][sparesArray[0][1]];
        for (int i = 1; i < sparesArray.length; i++) {
            int row = sparesArray[i][0];
            int colunm = sparesArray[i][1];
            revertArray[row][colunm] = sparesArray[i][2];
        }
        System.out.println("还原后的普通数组");
        //遍历还原后的稀疏数组
        for (int i = 0; i < revertArray.length; i++) {
            for (int j = 0; j < revertArray[i].length; j++) {
                System.out.print(revertArray[i][j]);
                System.out.print(" ");
            }
            System.out.println();
        }

输出结果