shanX
文章31
标签17
分类9
稀疏数组

稀疏数组

==

  1. 当一个数组中大部分元素为0时,或者为同一数值时,可以使用稀疏数组来保存该数组;
    稀疏数组处理方式:
  • 记录数一共有几行几列,有几种不同值;
  • 把具有不同值的元素和行列及值记录在一个小规模的数组中,从而缩小程序的规模;
  1. 原始数组
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    1    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    0    
0    0    0    0    0    0    0    0    0    0    0    
  1. 稀疏数组
| 行  | 列  | 值  |
---------------------
| 11  | 11  | 2  |
| 1   | 2   | 1  |
| 2   | 3   | 1  |
  1. 代码处理:
public class ArrayDemo03 {
    //稀疏数组
    public static void main(String[] args) {
        int[][] arr1 = new int[11][11];
        arr1[1][2] = 1;
        arr1[2][3] = 1;

        System.out.println("输出原始数组:");

        for (int[] ints : arr1) {
            for (int anInt : ints) {
                System.out.print(anInt + "\t");
            }
            System.out.print("\n");
        }

        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);


        System.out.println("===============遍历数组,将非0的值存储在稀疏数组中=====================");
        int[][] arr2 = new int[sum+1][3];

        arr2[0][0] = 11;
        arr2[0][1] = 11;
        arr2[0][2] = sum;

        //遍历数组,将非0的值存储在稀疏数组中
        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("=============================================");
        System.out.println("输出稀疏数组:");

        for (int i = 0; i < arr2.length; i++) {
            System.out.print(arr2[i][0] + "\t"
                +arr2[i][1]+"\t"
                +arr2[i][2]+"\n");
        }

        System.out.println("===============================================");
        System.out.println("还原");
        int[][] arr3 = new int[arr2[0][0]][arr2[0][1]];

        //给其他元素0
        for (int i = 1; i < arr2.length; i++) {
            arr3[arr2[i][0]][arr2[i][1]] = arr2[i][2];
        }

        //打印arr3
        System.out.println("输出还原的数组:");
        for (int[] ints : arr3) {
            for (int anInt : ints) {
                System.out.print(anInt + "\t");
            }
            System.out.println();
        }
    }
}
  1. 输出结果:
输出原始数组:
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    1    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    0    
0    0    0    0    0    0    0    0    0    0    0    
====================================
有效值得个数为:2
===============遍历数组,将非0的值存储在稀疏数组中=====================
=============================================
输出稀疏数组:
11    11    2
1    2    1
2    3    1
===============================================
还原
输出还原的数组:
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    1    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    0    
0    0    0    0    0    0    0    0    0    0    0    

Process finished with exit code 0

可以用来做棋盘

本文作者:shanX
本文链接:https://rhymexmove.github.io/2021/04/01/59f21206d8fb/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可