稀疏数组(java实现)

凯凯

• 稀疏数组：当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。稀疏数组的处理方法是:

  • 记录数组一共有几行几列，有多少个不同的值
  • 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

• 稀疏数组和二维数组的转化

  • 二维数组转稀疏数组的思路：
    • 遍历原始的二维数组，得到有效数据的个数sum
    • 根据sum就可以创建稀疏数组 sparseArr int [sum+1][3]
    • 将二维数组的有效数据存入到稀疏数组中
  • 稀疏数组转原始的二维数组的思路：
    • 先读取稀疏数组的第一个行，根据第一个行的数据创建原始的二维数组，比如上面的chessArr2=int[11][11];
    • 在读取稀疏数组后几行的数据，并赋予原始的二维数组

• 具体的代码实现：

  package com.atguigu.sparsearray;
  
  public class SparseArray {
  
  	public static void main(String[] args) {
  		//创建一个原始的二维数组
  		//0:表示没有棋子，1表示黑子，2表示白字
  		int[][] chessArr1=new int[11][11];
  		
  		chessArr1[1][2]=1;
  		chessArr1[2][3]=2;
  		//输出原始的二维数组
  		System.out.println("原始的二维数组");
  		for(int[] row:chessArr1) {
  			for(int item:row) {
  				System.out.printf("%dt",item);
  			}
  			System.out.println("");
  		}
  		//将二维数组转化为稀疏数组的思路
  		//1.先遍历二维数组，得到非0数据的个数
  		System.out.println("得到的稀疏数组为如下形式：");
  		int sum=0;
  		for(int i=0;i<11;i++) {
  			for(int j=0;j<11;j++) {
  				if(chessArr1[i][j]!=0) {
  					sum++;
  				}
  			}
  		}
  		System.out.println("有效数字的个数："+sum);
  		//2.创建对应的稀疏数组
  		int[][] sparseArr=new int[sum+1][3];
  		sparseArr[0][0]=11;
  		sparseArr[0][1]=11;
  		sparseArr[0][2]=sum;
  		//有效数字给给稀疏数组赋值
  		int row=1;
  		for(int i=0;i<11;i++) {
  			for(int j=0;j<11;j++) {
  				if(chessArr1[i][j]!=0) {
  					sparseArr[row][0]=i;
  					sparseArr[row][1]=j;
  					sparseArr[row][2]=chessArr1[i][j];
  					row++;
  				}
  			}
  		}
  		//打印输出的稀疏数组
  		for(int i=0;i 
  输出数组：