java稀疏数组与普通数组相互转化-蒲公英云

java稀疏数组与普通数组相互转化

稀疏矩阵

矩阵中非零元素的个数远远小于矩阵元素的总数，并且非零元素的分布没有规律，通常认为矩阵中非零元素的总数比上矩阵所有元素总数的值小于等于0.05时，则称该矩阵为稀疏矩阵(sparse matrix)，该比值称为这个矩阵的稠密度；与之相区别的是，如果非零元素的分布存在规律（如上三角矩阵、下三角矩阵、对角矩阵），则称该矩阵为特殊矩阵。

package com.cds.sparsearray;
public class SparseArrayDemo2 { 
    public static void main(String[] args) { 
        System.out.println("1. 新建数组");
        int[][] arr = new int[4][4];
        arr[1][1] = 1;
        arr[2][2] = 2;
        arr[3][2] = 3;
        //打印数组
        printArray(arr);
        System.out.println("2. 二维数组转稀疏数组");
        //二维数组转化为稀疏矩阵
        int[][] arrayToSparse = arrayToSparse(arr);
        //打印数组
        printArray(arrayToSparse);
        System.out.println("3. 稀疏数组转二维数组");
        //稀疏矩阵转化为二维数组
        int[][] spareseToArray = spareseToArray(arrayToSparse);
        //打印数组
        printArray(spareseToArray);
    }
    private static void printArray(int[][] arr) { 
        for (int[] is : arr) { 
            for (int is2 : is) { 
                System.out.printf("%d\t",is2);
            }
            System.out.println();
        }
    }
    private static int[][] arrayToSparse(int[][] arr) { 
        int row = arr.length;    //行数
        int columns = arr[0].length;    //列数 
            //3.2 获取非零元素的个数
        int count = 0;
        for (int[] is : arr) { 
            for (int is2 : is) { 
                if(is2 != 0) { 
                    count++;
                }
            }
        }
            //3.3 新建稀疏数组
        int[][] sparse = new int[count + 1][3];
        sparse[0][0] = row;
        sparse[0][1] = columns;
        sparse[0][2] = count;
            //3.4 将非零元素存入稀疏数组
        int num = 0;
        for (int i = 0; i < arr.length; i++) { 
            for (int j = 0; j < arr.length; j++) { 
                if(arr[i][j] != 0) { 
                    num++;
                    sparse[num][0] = i;
                    sparse[num][1] = j;
                    sparse[num][2] = arr[i][j];
                    }
                }
            }
        return sparse;
    }
    private static int[][] spareseToArray(int[][] sparse) { 
        int[][] arr2 = new int[ sparse[0][0] ][ sparse[0][1] ];
        //4.2 将稀疏数组中的数据放到数组中
        for (int i = 1; i < sparse.length; i++) { 
            arr2[sparse[i][0]][sparse[i][1]] = sparse[i][2];
        }
        return arr2;
    }
}