稀疏数组

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

2. 稀疏数组的处理方式：

• 记录数组一共有几行几列，有多少个不同值

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

 package com.wu.array;
 ​
 public class ArrayDemo08 {
     public static void main(String[] args) {
 ​
         //创建一个二维数组 11*11  0：没有棋子   1：白棋    2：黑棋
         int[][] array1 = new int[11][11];
         array1[1][2] = 1;
         array1[2][3] = 2;
 ​
         //输出原始数组
         System.out.println("输出原始数组");
 ​
         for (int[] a:array1){
             for (int b:a){
                 System.out.print(b+"\t");
             }
             System.out.println( );
         }
 ​
         //转换为稀疏数组保存
 ​
         //获取有效值个数
         int sum = 0;
         for (int i = 0; i <11 ; i++) {
             for (int j = 0; j < 11; j++) {
                 if (array1[i][j]!=0){
                     sum++;
                 }
             }
         }
         System.out.println("有效值个数为:"+sum);
         //创建一个稀疏数组
 ​
         int[][] array2 = new int[sum+1][3];
         array2[0][0] = 11;
         array2[0][1] = 11;
         array2[0][2] = sum;
 ​
         //遍历二维数组，将非0的值，存放到稀疏数组中
 ​
         int count = 0;
 ​
         for (int i = 0; i < array1.length; i++) {//循环array1的行
             for (int j = 0; j < array1[i].length; j++) {//循环array1的列
                 if (array1[i][j]!=0){//当array的  第i行   第j列不等于0时执行count++
                     count++;//array2的横坐标（每次遇到一个不为0就+1记录在稀疏数组中）  纵坐标是固定的
                     //稀疏数组只有三列
                     array2[count][0] = i;//存放二维数组中不为0的下标值（i 横坐标）数组从0开始
                     array2[count][1] = j;//存放二维数组中不为0的下标值（j 纵坐标）数组从0开始
                     array2[count][2] = array1[i][j];//将二维数组中不为0的值存放到稀疏数组中
                 }
             }
         }
 ​
         //输出稀疏数组
 ​
         System.out.println("输出稀疏数组");
         for (int i = 0; i < array2.length; i++) {
             System.out.println(  array2[i][0]+"\t"
                                 +array2[i][1]+"\t"
                                 +array2[i][2]+"\t");
         }
 ​
         //还原数组
 ​
         //1. 读取稀疏数组
 ​
         int[][] array3 = new int[array2[0][0]][array2[0][1]];
 ​
         //给其中的元素还原它的值
         for (int i = 1; i < array2.length; i++) {
             array3[array2[i][0]][array2[i][1]] = array2[i][2];
         }
         //打印
         System.out.println("还原原始数组");
 ​
         for (int[] a:array3){
             for (int b:a){
                 System.out.print(b+"\t");
             }
             System.out.println( );
         }
     }
 }