1.实际需求

五子棋程序中有存盘和复盘的功能。

image.png

2.分析问题

使用二维数组来存的话，会有很多默认的0值，也就是没有意义的值，此时需要引入稀疏数组来解决。

3.稀疏数组介绍

当一个数组中大部分元素的值为0，或者大部分元素的值相同时，可以使用稀疏数组来保存该数组中的元素。
稀疏数组是怎么设计的？
1.它是行数不确定，3列的一个数组。
2.第一行记录原始二维数组有多少行，多少列和多少个不同的值。
3.其它行用来记录这些值在二维数组的行，列和值。
例如：

image.png

• 稀疏数组第一行记录了目标二维数组中有6行，7列，8个不同的值（不包含0）.
• 第二行记录了22在二维数组中的行、列、值。

4.代码实现

image.png

4.1思路分析

• 二维数组转稀疏数组：
  1.遍历原始二维数组，找出数组中有效值个数sum.
  2.根据sum创建稀疏数组sparseArr = new int[sum+1][3]
  3.将二维数组中元素信息写到稀疏数组中
• 稀疏数组转二维数组
  1.根据稀疏数组第一行值创建二维数组，例如chessArr = new int[11][11].
  2.读取稀疏数组后几行数据赋值给二维数组即可。

package com.yc.day01;

import java.util.Arrays;

/**
 * 练习二维数组转稀疏数组
 * */
public class SparseArr {
    public static void main(String[] args) {
        int chessArr[][] = new int[11][11];
        chessArr[1][2] = 1;
        chessArr[2][3] = 2;
        System.out.println("原始二维数组：");
        printArr(chessArr);
        System.out.println("稀疏数组：");
        int[][] sparseArr = chessArrToSparseArr(chessArr);
        printArr(sparseArr);
        System.out.println("稀疏转二维数组：");
        int[][] newChessArr = sparseArrToChessArr(sparseArr);
        printArr(newChessArr);

    }
    /**二维数组转稀疏数组*/
    public static int[][] chessArrToSparseArr(int[][] chessArr){
        int sum = getValidNumCount(chessArr);
        int sparseArr[][] = new int[sum+1][3];
        setSparseValue(chessArr,sparseArr,sum);
        return sparseArr;
    }
    /**稀疏数组转二维数组*/
    public static int[][] sparseArrToChessArr(int[][] sparseArr){
        int row = sparseArr[0][0];
        int col = sparseArr[0][1];
        int[][] chessArr = new int[row][col];
        for(int i =1;i<sparseArr.length;i++){
            chessArr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        return chessArr;
    }
    /**打印数组*/
    public static void  printArr(int[][] chessArr){
        for (int i = 0; i < chessArr.length; i++) {
            for (int j = 0; j < chessArr[0].length; j++) {
                System.out.print(chessArr[i][j]+"\t");
            }
            System.out.println();
        }
    }
    /**获取二维数组中不为0的值的个数*/
    public static int getValidNumCount(int[][] chessArr){
        int count = 0;
        for (int i = 0; i < chessArr.length; i++) {
            for (int j = 0; j < chessArr[0].length; j++) {
               if(chessArr[i][j]!=0){
                   count++;
               }
            }
        }
        return count;
    }
    /**设置稀疏数组值*/
    public static void setSparseValue(int[][] chessArr,int[][] sparseArr,int sum){
        sparseArr[0][0] = chessArr.length;
        sparseArr[0][1] = chessArr[0].length;
        sparseArr[0][2] = sum;
        int count = 0;
        for (int i = 0; i < chessArr.length; i++) {
            for (int j = 0; j < chessArr[0].length; j++) {
                if(chessArr[i][j]!=0){
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr[i][j];
                }
            }
        }
    }
}

image.png