认识稀疏数组

作用

当一个数组中大部分元素为 0 、或者为同一个值得数组时，可以使用稀疏数组来保存该数组

特点

• 描述

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

• 图示

转换

二维数组转稀疏数组

• 思路

  1. 遍历原始的二维数组，得到有效数据的个数 sum
  2. 根据 sum 就可以创建稀疏数组 sparseArr int[sum+1][3]
  3. 将二维数组的有效数据存入到稀疏数组

• 实现

  :::details 点击查看代码

  /**
     * @description: 创建二维数组
     */
    function CreateDoubleArray(row, col) {
      let array = new Array();
      for (let i = 0; i < row; i++) {
        array[i] = new Array();
        for (let j = 0; j < col; j++) {
          array[i][j] = 0;
        }
      }
      return array;
    }
    /**
     * @description: 绘制二维数组
     */
    function DrawDoubleArray(array, row, col) {
      for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
          document.write(array[i][j] + " ");
        }
        document.write("<br/>");
      }
    }
    /**
     * @description: 创建稀疏数组
     */
    function CreateSparseArray(DenseArray, row, col) {
      let sum = 0; //记录密集数组中 不为0 的个数
      for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
          if (array[i][j] !== 0) {
            sum++;
          }
        }
      }
      let rowS = sum + 1;
      let colS = 3;
      let sparseArray = CreateDoubleArray(rowS, colS); //创建稀疏数组框架
      sparseArray[0][0] = row;
      sparseArray[0][1] = col;
      sparseArray[0][2] = sum;
      let count = 0; //记录行数
      for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
          if (array[i][j] !== 0) {
            count++;
            sparseArray[count][0] = i;
            sparseArray[count][1] = j;
            sparseArray[count][2] = array[i][j];
          }
        }
      }
      DrawDoubleArray(sparseArray,rowS,colS);
    }
    let array=CreateDoubleArray(10,10);
    array[2][3]=5;
    array[5][6]=29;
    array[9][3]=3;
    CreateSparseArray(array,10,10);

  :::

稀疏数组转换二维数组

• 思路

  1.先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组
  2.在读取稀疏数组后几行的数据，并赋给原始的二维数组

• 实现

  :::details 点击查看代码

   /**
     * @description: 创建二维数组
     */
    function CreateDoubleArray(row, col) {
      let array = new Array();
      for (let i = 0; i < row; i++) {
        array[i] = new Array();
        for (let j = 0; j < col; j++) {
          array[i][j] = 0;
        }
      }
      return array;
    }
    /**
     * @description: 绘制二维数组
     */
    function DrawDoubleArray(array, row, col) {
      for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
          document.write(array[i][j] + " ");
        }
        document.write("<br/>");
      }
    }
    /**
     * @description: 创建稀疏数组
     */
    function CreateSparseArray(DenseArray, row, col) {
      let sum = 0; //记录密集数组中 不为0 的个数
      for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
          if (array[i][j] !== 0) {
            sum++;
          }
        }
      }
      let rowS = sum + 1;
      let colS = 3;
      let sparseArray = CreateDoubleArray(rowS, colS); //创建稀疏数组框架
      sparseArray[0][0] = row;
      sparseArray[0][1] = col;
      sparseArray[0][2] = sum;
      let count = 0; //记录行数
      for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
          if (array[i][j] !== 0) {
            count++;
            sparseArray[count][0] = i;
            sparseArray[count][1] = j;
            sparseArray[count][2] = array[i][j];
          }
        }
      }
      return sparseArray;
    }
    /**
     * @description: 稀疏转密集
     */
    function SparseToDense(sparseArray){
      let row=sparseArray[0][0];
      let col=sparseArray[0][1];
      let array=CreateDoubleArray(row,col);
      for(let i=1;i<sparseArray.length;i++){
          array[sparseArray[i][0]][sparseArray[i][1]]=sparseArray[i][2];
      }
      return array
    }
    let array = CreateDoubleArray(10, 10);
    array[2][3] = 5;
    array[5][6] = 29;
    array[9][3] = 3;
    let sparseArray=CreateSparseArray(array,10,10);
    let arrays=SparseToDense(sparseArray);
    DrawDoubleArray(arrays,10,10);

  :::

应用