零号站台

  • 首页
  • 文章归档

  • 搜索
并发编程 data structure java

稀疏数组

发表于 2022-02-20 | 0 | 阅读次数 688

1、稀疏数组为n行3列,第一行分别存储二维数组的行数、列数及非无用元素的个数;其他行存储非无用元素的行、列和值;比如一个二维数组中的大部分元素是0,还有其他的少部分的非0值,则可以用稀疏数组来存储以减少其内存消耗或者磁盘存储时的文件大小。
1645354264808.png
2、代码示例


    public static void main(String[] args) {
        int[][] arr = new int[][]{{0,0,0,0,0,0,0,0,0,0},
                                  {0,0,2,0,0,2,0,0,1,0},
                                  {2,1,1,1,1,2,0,2,0,0},
                                  {0,2,1,1,1,1,2,0,0,0},
                                  {0,0,1,2,2,2,2,1,0,0},
                                  {0,1,1,2,2,2,2,1,0,0},
                                  {1,0,2,1,0,2,1,0,0,0},
                                  {0,0,0,0,0,0,2,0,0,0},
                                  {0,0,0,0,0,0,0,1,0,0},
                                  {0,0,0,0,0,0,0,0,0,0}};

        int[][] convert = convert(arr);
        for (int i = 0; i < convert.length; i++){
            for (int j = 0; j < convert[i].length; j++) {
                System.out.print(convert[i][j] + "\t");
            }
            System.out.println("\n");
        }
        int[][] recover = recover(convert);
        for (int[] ints : recover) {
            for (int anInt : ints) {
                System.out.print(anInt + "\t");
            }
            System.out.println("\n");
        }
    }

    /**
     * 将五子棋棋盘二维数组转换为稀疏数组
     * 其中 1为黑子 2为白子 0为无子
     */
    public static int[][] convert(int[][] checkerboard){
        if (checkerboard == null){
            return null;
        }
        //遍历二维数组获取棋子的个数
        int pieceNum = 0;
        for (int i = 0; i < checkerboard.length; i++){
            for (int j = 0; j < checkerboard[i].length; j++) {
                int piece = checkerboard[i][j];
                if (piece != 0 && piece != 1 && piece != 2){
                    throw new RuntimeException("位置" + i + "-" + j + "存在无效数据:" + piece);
                }
                if (piece == 1 || piece == 2){
                    pieceNum++;
                }
            }
        }
        if (pieceNum == 0){
            return null;
        }
        //创建稀疏数组
        int[][] sparseArr = new int[pieceNum + 1][3];
        sparseArr[0] = new int[]{checkerboard.length,checkerboard[0].length,pieceNum};
        int row = 1;
        for (int i = 0; i < checkerboard.length; i++){
            for (int j = 0; j < checkerboard[i].length; j++) {
                if (checkerboard[i][j] != 0){
                    sparseArr[row++] =  new int[]{i,j,checkerboard[i][j]};
                }
            }
        }
        return sparseArr;
    }

    /**
     * 稀疏数组恢复为二维数组
     */
    public static int[][] recover(int[][] sparseArr){
        if (sparseArr == null){
            return null;
        }
        int[][] checkerboard = new int[sparseArr[0][0]][sparseArr[0][1]];
        for (int i = 1; i < sparseArr.length; i++) {
            checkerboard[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        return checkerboard;
    }
}

  • 本文作者: 妙哉
  • 本文链接: /archives/sparsearray
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
# java # data structure
sychronized锁范围
  • 文章目录
  • 站点概览
妙哉

妙哉

2 日志
4 分类
3 标签
RSS
Creative Commons
友链
  • 士子☀的博客
© 2023 妙哉
京ICP备2020043543号-1