稀疏数组的实现-蒲公英云

稀疏数组的实现

package sparsearray;
/*
*
* 现在有一数组arr
0   0   0   0   0   0   0   0   0   0   0
0   0   1   0   0   0   0   0   0   0   0
0   0   0   2   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   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，或者同一个值的数组时，可以使用稀疏数组来保存该数组。
* 处理方法：
* 1）记录数组一共有几行几列，有多少个不同的值
* 2） 把存储元素的行、列、值存储在一个小规模的数组中，从而缩小程序规模
* 转换为稀疏数组sparseArr后
* 行  列 值
* 11 11 2
* 1  2  1
* 2  3  2
* sparseArr[0][1] sparseArr[0][1]  sparseArr[0][2]分别存储原二维数组的行、列、有值元素个数 
* 这样只需要3*3的二维数组就存储了原来11*11的二维数组存储的内容，大大节省了空间
* 
*
*
*
* */
public class SparseArray { 
    //初始化一个数组
   public static int[][] initArr(){ 
        int arr[][] = new int[11][11];
        for (int i = 0; i<11;i++){ 
            for (int j = 0; j<11;j++){ 
                arr[i][j] = 0;
            }
        }
        arr[1][2] = 1;
        arr[2][3] = 2;
        return arr;
   }
    public static void main(String[] args) { 
        int arr[][] = initArr();
        int sparseArr[][] = toSparseArray(arr);
        printArr(sparseArr);
        int arr1[][] = toArr(sparseArr);
        printArr(arr1);
    }
    //二维数组转换为稀疏数组
    /*
    * 1.得到元素的数目num
    * 2.初始化一个数组sparseArr[num+1][3]
    * 3.遍历二维数组，把不为0的元素的行，列，值赋值给sparseArr[curPos]
    *
    * */
    public static int[][] toSparseArray(int arr[][]){ 
        int m = arr.length;
        int n = arr[0].length;
        int num = 0;
        for (int i=0;i<arr.length;i++){ 
            for (int j =0;j<arr[i].length;j++){ 
                if (arr[i][j]!=0){ 
                    num++;
                }
                System.out.print(arr[i][j]+" ");
            }
            System.out.println();
        }
        int sparseArr[][] = new int[num+1][3];
        int curPos = 0;
        sparseArr[curPos++] = new int[]{ m,n,num};
        for (int i=0;i<arr.length;i++){ 
            for (int j =0;j<arr[i].length;j++){ 
                if (arr[i][j]!=0){ 
                    sparseArr[curPos++]=new int[]{ i,j,arr[i][j]};
                }
            }
        }
        return sparseArr;
    }
    /*
    * 打印二维数组
    * */
    public static void printArr(int arr[][]){ 
        for (int i=0;i<arr.length;i++){ 
            for (int j =0;j<arr[i].length;j++){ 
                System.out.print(arr[i][j]+" " );
            }
            System.out.println();
        }
    }
    /*
    *
    * 稀疏数组转换为二维数组
    * 1.获取二维数组的行m和列n从稀疏数组的第一行获取sparseArr[0]
    * 2.初始化二维数组arr[m][n]
    * 3.遍历稀疏数组，给二维数组赋值
    *
    * */
    public static int[][] toArr(int sparseArr[][]){ 
        int m =sparseArr[0][0];
        int n = sparseArr[0][1];
        int [][]arr = new int[m][n];
        for (int i= 1;i<sparseArr.length;i++){ 
            //System.out.println(sparseArr[i][0] + " " + sparseArr[i][1] +" " +sparseArr[i][2]);
            arr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        return arr;
    }
}