目录

稀疏数组

实际问题

https://gitee.com/lienhui68/picStore/raw/master/null/20200615075055.png 如上图11*11的棋盘,现在需要做存盘和复盘的功能,如何处理?

分析问题

首先想到的使用二维数组表示棋子所在位置及自身值,但是如上图所示有很多默认值,如果这样记录会有许多没有意义的数据。

处理思路

  1. 记录数组共有几行几列,有多少个不同值
  2. 把不同值记录在一个小规模的数组中
  3. 稀疏数组的第一行记录原始数组的行数、列数、有效元素个数;从稀疏数组的第二行开始记录有效元素的所在行、所在列以及值。 https://gitee.com/lienhui68/picStore/raw/master/null/20200615080134.png

编程实现

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
package com.eh.ftd.dsa.ds;

/**
 * 稀疏数组
 * 棋盘 有白子和黑子,使用稀疏数组来优化存盘并提供功能予以复盘
 *
 * @author David Li
 * @create 2020/06/11 16:39
 */
public class SparseArr {

    /**
     * 打印棋盘,1 表示白子;2表示黑子
     *
     * @param chessBoard
     */
    public static void printChessBoard(int[][] chessBoard) {
        if (chessBoard.length < 2) {
            throw new RuntimeException("输入有误");
        }
        // 获取棋盘行数
        int rowNumber = chessBoard.length;
        // 获取棋盘列数
        int colNumber = chessBoard[0].length;
        // 遍历棋盘并打印 1表示白子;2表示黑子
        for (int row = 0; row < rowNumber; row++) {
            for (int col = 0; col < colNumber; col++) {
                System.out.printf(chessBoard[row][col] + " ");
            }
            // 换行
            System.out.println();
        }
    }

    /**
     * 将原始棋盘转换成稀疏数组
     *
     * @param chessBoard
     * @return
     */
    public static int[][] convert2SparseArr(int[][] chessBoard) {
        if (chessBoard.length < 2) {
            throw new RuntimeException("输入有误");
        }
        // 获取棋盘行数
        int rowNumber = chessBoard.length;
        // 获取棋盘列数
        int colNumber = chessBoard[0].length;
        // 活跃棋格数目
        int activeNumber = 0;
        // 遍历棋盘获取活跃棋格数
        for (int row = 0; row < rowNumber; row++) {
            for (int col = 0; col < colNumber; col++) {
                if (chessBoard[row][col] > 0) {
                    activeNumber++;
                }
            }
        }
        // 组装稀疏数组

        // 第一行
        int[][] sparseArr = new int[activeNumber + 1][3];
        sparseArr[0][0] = rowNumber;
        sparseArr[0][1] = colNumber;
        sparseArr[0][2] = activeNumber;

        // 剩下行
        int temp = 1;
        for (int row = 0; row < rowNumber; row++) {
            for (int col = 0; col < colNumber; col++) {
                if (chessBoard[row][col] > 0) {
                    sparseArr[temp][0] = row;
                    sparseArr[temp][1] = col;
                    sparseArr[temp][2] = chessBoard[row][col];
                    temp++;
                }
            }
        }

        return sparseArr;
    }

    /**
     * 将稀疏数组转换成原始数组, 模拟复盘操作
     *
     * @param sparseArr
     * @return
     */
    public static int[][] convert2OriginalChessBoard(int[][] sparseArr) {
        // 获取行列数和活跃棋格数
        int rowNumber = sparseArr[0][0];
        int colNumber = sparseArr[0][1];
        int activeNumber = sparseArr[0][2];
        // 遍历稀疏数组 将值设置到原始数组
        int[][] originChessBoard = new int[rowNumber][colNumber];
        for (int i = 1; i <= activeNumber; i++) {
            // 稀疏数组的行列值分别对应原始数组的行列值
            originChessBoard[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        return originChessBoard;
    }


    public static void main(String[] args) {
        // 构造原始棋盘 0-空格 1-白子 2-黑子
        int[][] chessBoard = new int[11][11];
        chessBoard[1][2] = 2;
        chessBoard[2][1] = 1;
        chessBoard[3][3] = 2;
        System.out.println("=======原始棋盘==========");
        printChessBoard(chessBoard);
        // 转换成稀疏数组
        int[][] sparseArr = convert2SparseArr(chessBoard);
        System.out.println("=======转换后的稀疏数组==========");
        printChessBoard(sparseArr);
        // 转换成原始数组,模拟复盘
        int[][] originChessBoard = convert2OriginalChessBoard(sparseArr);
        System.out.println("=======稀疏数组复盘后的原始棋盘==========");
        printChessBoard(originChessBoard);
    }
}

运行结果: https://gitee.com/lienhui68/picStore/raw/master/null/20200615081850.png

扩展

  1. 稀疏数组主要应用于压缩数据
  2. 如果是三维数组比如空间数据,同样可以使用稀疏数组(xnum,ynum,znum,activeNum)(x,y,z,val)来表示。