1.實際需求

五子棋程序中有存盤和復(fù)盤的功能。

image.png

2.分析問題

使用二維數(shù)組來存的話，會有很多默認(rèn)的0值，也就是沒有意義的值，此時需要引入稀疏數(shù)組來解決。

3.稀疏數(shù)組介紹

當(dāng)一個數(shù)組中大部分元素的值為0，或者大部分元素的值相同時，可以使用稀疏數(shù)組來保存該數(shù)組中的元素。
稀疏數(shù)組是怎么設(shè)計的？
1.它是行數(shù)不確定，3列的一個數(shù)組。
2.第一行記錄原始二維數(shù)組有多少行，多少列和多少個不同的值。
3.其它行用來記錄這些值在二維數(shù)組的行，列和值。
例如：

image.png

• 稀疏數(shù)組第一行記錄了目標(biāo)二維數(shù)組中有6行，7列，8個不同的值（不包含0）.
• 第二行記錄了22在二維數(shù)組中的行、列、值。

4.代碼實現(xiàn)

image.png

4.1思路分析

• 二維數(shù)組轉(zhuǎn)稀疏數(shù)組：
  1.遍歷原始二維數(shù)組，找出數(shù)組中有效值個數(shù)sum.
  2.根據(jù)sum創(chuàng)建稀疏數(shù)組sparseArr = new int[sum+1][3]
  3.將二維數(shù)組中元素信息寫到稀疏數(shù)組中
• 稀疏數(shù)組轉(zhuǎn)二維數(shù)組
  1.根據(jù)稀疏數(shù)組第一行值創(chuàng)建二維數(shù)組，例如chessArr = new int[11][11].
  2.讀取稀疏數(shù)組后幾行數(shù)據(jù)賦值給二維數(shù)組即可。

package com.yc.day01;

import java.util.Arrays;

/**
 * 練習(xí)二維數(shù)組轉(zhuǎn)稀疏數(shù)組
 * */
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("原始二維數(shù)組：");
        printArr(chessArr);
        System.out.println("稀疏數(shù)組：");
        int[][] sparseArr = chessArrToSparseArr(chessArr);
        printArr(sparseArr);
        System.out.println("稀疏轉(zhuǎn)二維數(shù)組：");
        int[][] newChessArr = sparseArrToChessArr(sparseArr);
        printArr(newChessArr);

    }
    /**二維數(shù)組轉(zhuǎn)稀疏數(shù)組*/
    public static int[][] chessArrToSparseArr(int[][] chessArr){
        int sum = getValidNumCount(chessArr);
        int sparseArr[][] = new int[sum+1][3];
        setSparseValue(chessArr,sparseArr,sum);
        return sparseArr;
    }
    /**稀疏數(shù)組轉(zhuǎn)二維數(shù)組*/
    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;
    }
    /**打印數(shù)組*/
    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();
        }
    }
    /**獲取二維數(shù)組中不為0的值的個數(shù)*/
    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;
    }
    /**設(shè)置稀疏數(shù)組值*/
    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