稀疏数组

• 介绍

  • 当一个数组中大部分元素为0，或为同一数值时，可以使用稀疏数组来保存该数组，叫做压缩算法
  • 处理方式
    • 记录数组一共几行几列，有多少不同值
    • 把具有不同值的元素找出来，记录其行列和具体值信息，组成一个小规模的数组，从而缩小程序的规模

• 代码演示

  public class Demo14 {
      public static void main(String[] args) {    //稀疏数组：围棋案例
          int[][] arr1 = new int[11][11];//创建一个二维数组11行11列
          arr1[1][2] = 1;                  //0：没有棋子 1：黑棋 2：白旗
          arr1[2][3] = 2;
          System.out.println("输出原来的数组");
  
          for (int[] ints : arr1) {       //遍历原数组
              for (int anInt : ints) {
                  System.out.print(anInt + "\t");
              }
              System.out.println();
          }
          System.out.println("================================");
          int sum = 0;                     //获取有效值的个数
          for (int i = 0; i < 11; i++) {
              for (int j = 0; j < 11; j++) {
                  if (arr1[i][j] != 0) {
                      sum++;
                  }
              }
          }
          System.out.println("有效值的个数：" + sum);
  
          int[][] arr2 = new int[sum + 1][3]; //创建一个稀疏数组的数组
          arr2[0][0] = 11;
          arr2[0][1] = 11;
          arr2[0][2] = sum;
  
          int count = 0;  //遍历二维数组，将非零的值存放在稀疏数组中
          for (int i = 0; i < arr1.length; i++) {
              for (int j = 0; j < arr1[i].length; j++) {
                  if (arr1[i][j] != 0) {
                      count++;
                      arr2[count][0] = i;
                      arr2[count][1] = j;
                      arr2[count][2] = arr1[i][j];
                  }
              }
          }
          System.out.println("稀疏数组");
          for (int i = 0; i < arr2.length; i++) { //输出稀疏数组
              System.out.println(arr2[i][0] + "\t"
                      + arr2[i][1] + "\t"
                      + arr2[i][2] + "\t");
  
          }
          System.out.println("================================");
          System.out.println("还原稀疏数组");
  
          int[][] arr3 = new int[arr2[0][0]][arr2[0][1]];//读取稀疏数组
          for (int i = 1; i < arr2.length; i++) {//将其中的元素还原成原值
              arr3[arr2[i][0]][arr2[i][1]] = arr2[i][2];
          }
          System.out.println("输出原始的数组");
          for (int[] ints : arr3) {
              for (int anInt : ints) {
                  System.out.print(anInt + "\t");
              }
              System.out.println();
          }
  
      }
  }
  

022-稀疏数组

原文：https://www.cnblogs.com/xianjingze/p/14394188.html