稀疏数组的实现

谁践踏了优雅 2022-10-22 04:10 18阅读 0赞

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