数据结构与算法(Java版)_02_SparseArray稀疏数组

稀疏数组使用场景:

当一个二维数组中很多元素为0或为同一个值时,可以用稀疏数组保存该数组。

稀疏数组使用方法

 

1.先统计原二维数组行和列数,以及有多少个不为0的数或多少个不同的数。

2.创建一个二维数组作为稀疏数组,第一行分别存放行数、列数、多少个不为0的数或多少个不同的数。

3.遍历数组,将每个不为0的数或每个不同的数的行标、列标、值分别存放到稀疏数组中。

数据结构与算法(Java版)_02_SparseArray稀疏数组

使用Java代码实现:

public static void main(String[] args) {
        //创建棋盘并初始化棋子位置,1代表黑子,2代表蓝子
        int[][] chessBoard = new int[11][11];
        chessBoard[1][1] = 1;
        chessBoard[2][2] = 2;
        chessBoard[4][7] = 2;
        
        //统计非零数据总数
        int notZeros = 0;
        for(int[] row : chessBoard) {
            for(int element : row) {
                if(0!=element) notZeros++;
            }
        }
        //创建稀松数组并赋值
        int[][] sparseArr= new int[notZeros+1][3];
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = notZeros;
        int count = 0;
        for(int i=0;i<chessBoard.length;i++) {
            for(int j=0;j<chessBoard[0].length;j++) {
                if(0!=chessBoard[i][j]) {
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessBoard[i][j];
                }
            }
        }
        
        //解析稀松数组为普通数组
        int newRow = sparseArr[0][0];
        int newCol = sparseArr[0][1];
        int[][] chessBoard1 = new int[newRow][newCol];
        for(int i=1;i<sparseArr.length;i++) {
                int row1 = sparseArr[i][0];
                int col1 = sparseArr[i][1];
                int val = sparseArr[i][2];
                chessBoard1[row1][col1] = val;
        }
        sop("初始棋盘为:\n","");
        //打印棋盘
        for(int[] row : chessBoard) {
            for(int element : row) {
                sop("%d ",element);
            }
            sop("\n","");
        }
        sop("存储棋盘的稀松数组为:\n","");
        //打印稀松数组
        for(int[] row : sparseArr) {
            for(int element : row) {
                sop("%d ",element);
            }
            sop("\n","");
        }
        sop("稀松数组转棋盘为:\n","");
        //打印棋盘
        for(int[] row : chessBoard1) {
            for(int element : row) {
                sop("%d ",element);
            }
            sop("\n","");
        }
        //sop("%d",notZeros);
    }
    public static void sop(String str,Object obj1) {
        System.out.printf(str,obj1);
    }
}

实现效果:

数据结构与算法(Java版)_02_SparseArray稀疏数组

 

 

 

 

public static void main(String[] args) {

//创建棋盘并初始化棋子位置,1代表黑子,2代表蓝子

int[][] chessBoard = new int[11][11];

chessBoard[1][1] = 1;

chessBoard[2][2] = 2;

chessBoard[4][7] = 2;

 

//统计非零数据总数

int notZeros = 0;

for(int[] row : chessBoard) {

for(int element : row) {

if(0!=element) notZeros++;

}

}

//创建稀松数组并赋值

int[][] sparseArr= new int[notZeros+1][3];

sparseArr[0][0] = 11;

sparseArr[0][1] = 11;

sparseArr[0][2] = notZeros;

int count = 0;

for(int i=0;i<chessBoard.length;i++) {

for(int j=0;j<chessBoard[0].length;j++) {

if(0!=chessBoard[i][j]) {

count++;

sparseArr[count][0] = i;

sparseArr[count][1] = j;

sparseArr[count][2] = chessBoard[i][j];

}

}

}

 

//解析稀松数组为普通数组

int newRow = sparseArr[0][0];

int newCol = sparseArr[0][1];

int[][] chessBoard1 = new int[newRow][newCol];

for(int i=1;i<sparseArr.length;i++) {

int row1 = sparseArr[i][0];

int col1 = sparseArr[i][1];

int val = sparseArr[i][2];

chessBoard1[row1][col1] = val;

}

sop("初始棋盘为:\n","");

//打印棋盘

for(int[] row : chessBoard) {

for(int element : row) {

sop("%d ",element);

}

sop("\n","");

}

sop("存储棋盘的稀松数组为:\n","");

//打印稀松数组

for(int[] row : sparseArr) {

for(int element : row) {

sop("%d ",element);

}

sop("\n","");

}

sop("稀松数组转棋盘为:\n","");

//打印棋盘

for(int[] row : chessBoard1) {

for(int element : row) {

sop("%d ",element);

}

sop("\n","");

}

//sop("%d",notZeros);

}

public static void sop(String str,Object obj1) {

System.out.printf(str,obj1);

}

上一篇:利用深度优先搜索等算法实现围棋棋盘控制


下一篇:leetcode-51:N 皇后