稀疏数组

一、稀疏数组和队列

  1、稀疏数组

    基本功能

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

  2.处理方法

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

  如图，把一个6X7的二维数组变为了一个9X3的稀疏数组。其中

• 第一行保存的是原二维数组的行、列以及非0值的个数
• 第二到九行保存的是每个非0值所在的位置及其数值

3.转换思路

  二维数组转稀疏数组

• 遍历二维数组，得到二维数组中有效值的个数sum
• 创建稀疏数组，有sum+1行，3列（固定）
• 将二维数组中的有效值存入稀疏数组中

  稀疏数组转二维数组

• 先读取稀疏数组的第一行（保存二维数组的行列信息），还原二维数组
• 读取稀疏数组的其他行，将值赋给二维数组的对应位置上的数

代码

public class Demo2 {   public static void main(String[] args) {      //创建一个二维数组      int[][] arr1 = new int[11][11];      //向二维数组里放值      arr1[1][2] = 1;      arr1[2][3] = 2;      arr1[3][4] = 3;      //打印二维数组      System.out.println("遍历二维数组");      for (int i = 0; i < arr1.length; i++) {         for (int j = 0; j < arr1[0].length; j++) {            System.out.print(arr1[i][j] + "   ");         }         System.out.println();      }      //二位数组----->稀疏数组      //遍历二维数组中有效值的个数,用sum来记录      int sum = 0;      for (int i = 0; i < arr1.length; i++) {         for (int j = 0; j < arr1[0].length; j++) {            if (arr1[i][j] != 0) {               //二维数组中元素不为0即为有效值               sum++;            }         }      }      //创建稀疏数组      //行数为sum+1，第一行用于保存二维数组的行列及有效值个数，列数固定为3      int[][] sparseArr = new int[sum + 1][3];      //存入二维数组的行列及有效值个数      sparseArr[0][0] = arr1.length;      sparseArr[0][1] = arr1[0].length;      sparseArr[0][2] = sum;      //再次遍历二维数组，将有效值存入稀疏数组      //用于保存稀疏数组的行数      int count = 1;      for (int i = 0; i < arr1.length; i++) {         for (int j = 0; j < arr1[0].length; j++) {            if (arr1[i][j] != 0) {               //将值存入稀疏数组               sparseArr[count][0] = i;               sparseArr[count][1] = j;               sparseArr[count][2] = arr1[i][j];               count++;            }         }      }      //打印稀疏数组      System.out.println("遍历稀疏数组");      for (int i = 0; i < sparseArr.length; i++) {         for (int j = 0; j < sparseArr[0].length; j++) {            System.out.print(sparseArr[i][j] + "   ");         }         System.out.println();      }      //稀疏数组------>二维数组      //先得到二位数组的行列数      int row = sparseArr[0][0];      int col = sparseArr[0][1];      int[][] arr2 = new int[row][col];      //遍历稀疏数组，同时给二维数组赋值      for (int i = 1; i < sparseArr.length; i++) {         row = sparseArr[i][0];         col = sparseArr[i][1];         //该位置上对应的值         int val = sparseArr[i][2];         arr2[row][col] = val;      }      //打印二维数组      System.out.println("遍历还原后的二维数组");      for (int i = 0; i < arr2.length; i++) {         for (int j = 0; j < arr2[0].length; j++) {            System.out.print(arr2[i][j] + "   ");         }         System.out.println();      }   }}

运行结果

遍历二维数组0   0   0   0   0   0   0   0   0   0   0   0   0   1   0   0   0   0   0   0   0   0   0   0   0   2   0   0   0   0   0   0   0   0   0   0   0   3   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   遍历稀疏数组11   11   3   1   2   1   2   3   2   3   4   3   遍历还原后的二维数组0   0   0   0   0   0   0   0   0   0   0   0   0   1   0   0   0   0   0   0   0   0   0   0   0   2   0   0   0   0   0   0   0   0   0   0   0   3   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0