Java二维数组与稀疏数组相互转换实现详解

目录
  • 一、稀疏数组
    • 1、什么是稀疏数组
    • 2、图示
    • 3、稀疏数组的表达方式
  • 二、二维数组→稀疏数组
  • 三、稀疏数组→二维数组

一、稀疏数组

1、什么是稀疏数组

当一个数组中大部分元素为0,或者为同一个值的数组时,可以用稀疏数组来保存该数组。稀疏数组,记录一共有几行几列,有多少个不为零的值或相同的值。

简单来说就是将大规模的数组缩小成小规模的数据,从而减少空间浪费。

2、图示

上面的图示中,左侧是二维数组,右侧是稀疏数组,将二维数组转成稀疏数组,明显的可以看出空间减少了,可以有效的节约空间,提高效率。那么二维数组怎么生成稀疏数组呢?其实很简单,因为二维数组有特定的格式,按格式将二维数组中的数据放入稀疏数组即可。

3、稀疏数组的表达方式

稀疏数组的列是固定的,只有三列,第一列表示二维数组的行,第二列表示二维数组的列,第三列表示二维数组非零数的个数。稀疏数组的第一行是固定的,用来表示总行数,总列数,总个数。其余行数根据个数而定。

二、二维数组→稀疏数组

根据上图所示:

第一步:创建二维数组

//首先创建二维数组
int[][] ChessArr1 = new int[11][11];
//赋值
ChessArr1[1][2] = 1;
ChessArr1[2][3] = 2;
//循环遍历得到非零个数
int num = 0;
for(int[] row : ChessArr1) {
   for(int data : row) {
       if(data != 0) {
           num++;
        }
   }
}

上面用到了增强for循环,第一个增强for循环表示每一个row代表一行(二维数组的行)也就相当与一维数组,第二个增强for循环再遍历一维数组得到每一个数据data来进行判断是否是非零数。

第二步:创建稀疏数组,并赋值

int[][] SparseArr = new int[num + 1][3];
//第一行赋值
SparseArr[0][0] = 11;
SparseArr[0][1] = 11;
SparseArr[0][2] = num;

前面分析的时候说了,第一行是固定的,二维数组的大小是知道的,所以行列的总数可以直接赋值,总有效个数也求了,也可以直接赋值。

第三步:遍历二维数组并赋值给稀疏数组

        int count = 0;
        for(int i = 0; i < 11; i++) {
            for(int j = 0; j < 11; j++) {
                if(ChessArr1[i][j] != 0) {
                    count++;
                    SparseArr[count][0] = i;
                    SparseArr[count][1] = j;
                    SparseArr[count][2] = ChessArr1[i][j];
                }
            }
        }

遍历二维数组,判断条件是这个数不等于零,此处需要一个计数变量,每符合一个非零数,计数变量就加一,可以用来表示稀疏数组的第几行,稀疏数组的列数是固定的,所以找到后直接进行赋值操作。

最后打印稀疏数组即可。

完整代码

        //首先创建二维数组
        int[][] ChessArr1 = new int[11][11];
        //赋值
        ChessArr1[1][2] = 1;
        ChessArr1[2][3] = 2;
        //将原始数组转 换成 稀疏数组
        //1、先遍历原始数组得到非0数的个数
        int num = 0;
        for(int[] row : ChessArr1) {
            for(int data : row) {
                if(data != 0) {
                    num++;
                }
            }
        }
        //2、创建 稀疏数组
        int[][] SparseArr = new int[num + 1][3];
        //3、第一行赋值
        SparseArr[0][0] = 11;
        SparseArr[0][1] = 11;
        SparseArr[0][2] = num;
        //4、循环赋非0值
        int count = 0;
        for(int i = 0; i < 11; i++) {
            for(int j = 0; j < 11; j++) {
                if(ChessArr1[i][j] != 0) {
                    count++;
                    SparseArr[count][0] = i;
                    SparseArr[count][1] = j;
                    SparseArr[count][2] = ChessArr1[i][j];
                }
            }
        }
        //5、打印稀疏数组
        System.out.println("\n===打印稀疏数组===");
        for(int[] row : SparseArr) {
            for(int data : row) {
                System.out.printf("%d\t",data);
            }
            System.out.println();
        }

三、稀疏数组→二维数组

第一步:创建新的二维数组

//1、定义一个新的二维数组
int[][] ChessArr2 = new int[SparseArr[0][0]][SparseArr[0][1]];

二维数组的大小来自稀疏数组的第一行第一列和第一行第二列,也就是 SparseArr[0][0] 和 SparseArr[0][1] ;初始状态下的二维数组数据全为零。

第二步:循环遍历并赋值

        //2、赋值
        for(int i = 1; i <= SparseArr[0][2]; i++) {
            ChessArr2[SparseArr[i][0]][SparseArr[i][1]] = SparseArr[i][2];
        }

因为除了少数是有效个数,其他全是零,所以我们只需要遍历有效个数。i 表示第几个有效个数也表示当前这个数在稀疏数组中的行,如上图所示:如 i = 1,表示在稀疏数组的第一行,它在二维数组中的位置为 (1,2),数值为 1 ;所以行和列分别是SparseArr[1][0]和SparseArr[1][1],数值为SparseArr[1][2]。

所以赋值表达式为:ChessArr2[SparseArr[i][0]][SparseArr[i][1]] = SparseArr[i][2]。

完整代码

        //将稀疏数组 转换成 二维数组
        //1、定义一个新的二维数组
        int[][] ChessArr2 = new int[SparseArr[0][0]][SparseArr[0][1]];
        //2、赋值
        for(int i = 1; i <= SparseArr[0][2]; i++) {
            ChessArr2[SparseArr[i][0]][SparseArr[i][1]] = SparseArr[i][2];
        }
        //3、打印新的二维数组
        System.out.println("\n===新的二维数组===");
        for(int[] row : ChessArr2) {
            for(int data : row) {
                System.out.printf("%d\t",data);
            }
            System.out.println();
        }

到此这篇关于Java二维数组与稀疏数组相互转换实现详解的文章就介绍到这了,更多相关Java二维数组与稀疏数组转换内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • java数据结构基础:稀疏数组

    目录 稀疏数组: 实现思路: 举例: 二维数组转稀疏数组实现思路: 稀疏数组恢复二维数组实现思路: 代码实现: 输出结果: 总结 稀疏数组: 当一个二维数组中大部份的值为0,或者为同一值的时候,可以用稀疏数组来保存 实现思路: 记录二维数组有多少行多少列.多少个不同的值 把不同的值按照所在行列,记录在一个规模较小的数组中 举例: 11×11的二维数组: 对应的稀疏数组: 其中,第一行分别为,原二维数组总行数.总列数.不为0的数的个数 之后几行的每一列分别代表所在行.所在列.值 二维数组转稀疏数组

  • Java数据结构实现二维数组与稀疏数组转换详解

    基本介绍 当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组. 稀疏数组的处理方法是: ①记录数组一共有几行几列,有多少个不同的值(0除外). ②把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模. 二维数组转稀疏数组: ①遍历原始的二维数组,得到有效数据的个数 sum(除0外不同值) ②根据 sum 创建稀疏数组 sparseArr int[sum+1][3] ③将二维数组的有效数据数据存入到稀疏数组 (稀疏数组的第一行,三列分别记录二维数组

  • java数据结构算法稀疏数组示例详解

    目录 一.什么是稀疏数组 二.场景用法 1.二维数组转稀疏数组思路 2.稀疏数组转二维数组思路 3.代码实现 一.什么是稀疏数组 当一个数组a中大部分元素为0,或者为同一个值,那么可以用稀疏数组b来保存数组a. 首先,稀疏数组是一个数组,然后以一种特定的方式来保存上述的数组a,具体处理方法: 记录数组a一共有几行几列 记录a中有多少个不同的值 最后记录不同值的元素所在行列,以及具体的值,放在一个小规模的数组里,以缩小程序的规模. 这个小规模的数组,就是稀疏数组. 举个栗子,左侧是一个二维数组,一

  • Java 轻松实现二维数组与稀疏数组互转

    目录 二维数组 稀疏数组 1.稀疏算法的基本介绍 2.稀疏算法的处理方式 二维数组转稀疏数组的思路 二维数组 二维数组本质上是以数组作为数组元素的数组,即“数组的数组”,类型说明符 数组名[常量表达式][常量表达式].二维数组又称为矩阵,行列数相等的矩阵称为方阵.对称矩阵a[i][j] = a[j][i],对角矩阵:n阶方阵主对角线外都是零元素. 稀疏数组 1.稀疏算法的基本介绍 当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组.从而减少计算机不必要的内存开销.

  • Java实现二维数组和稀疏数组之间的转换

    前言 用Java实现二维数据和稀疏数组之间的转换 1. 需求和思路分析 1.1 以二维数组的格式模拟棋盘.地图等类似的二维结构为基础,与稀疏数组之间进行转化. 1.2 思路分析 二维数组转化为稀疏数组 遍历原始的二维数组,得到有效数据个数 sum 根据sum就可以创建稀疏数组sparseArr int[sunm+1][3] 将二维数组的有效数据存入到稀疏数组 稀疏数组转为二维数组 先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组 再读取稀疏数组后几行的数据,并赋给原始的二维数组即可.

  • java稀疏数组的示例代码

    稀疏组织 当一个数组中大部分元素为0,或者为同一个值的数组时,可以用稀疏数组来保存该数组 稀疏数组,记录一共有几行几列,有多少个不同值 把具有不同值的元素和行里了及值记录在一个小规模的数组中,从而缩小程序的规模! 我们定义一下原始数组: 原始数组如下: 0 0 3 0 0 0 0 0 0 4 0 0 0 5 0 0 0 6 0 0 0 0 0 0 0 可以看出,这个数组大部分都是0,我们可以把这个数组转化为稀疏数组 稀疏数组第一行存放的分别是总行数,总列数和存放的数据总数 //因为数组的下标是从

  • 浅谈Java数据结构之稀疏数组知识总结

    稀疏数组 当一个数组中的元素大多为0或者相同元素的时候,可以用稀疏数组来压缩 稀疏数组只记录 行row 列col 值value 将下列的二维数组转为稀疏数组,如下两图所示 1.实现二维数组转为稀疏数组的步骤: 遍历数组,得到数组中 不为0的个数,并记录为sum,作为稀疏数组第0行的 value 遍历数组,将数组中不为0的数的行和列和值分别写入稀疏数组的 row col val 中 代码实现: public class SparseArray { public static void main(S

  • Java数据结构之稀疏数组的实现与应用

    目录 1.稀疏数组引入 1.1 使用场景 1.2 稀疏数组简介 2.稀疏数组的实现 2.1 案例概述 2.2 思路分析 2.3 代码实现 1.稀疏数组引入 1.1 使用场景 笔者在课程设计中曾写过一个扫雷小游戏,为了便于讲解,我们来做个简化(实际比这个复杂),只考虑当前位置有雷与无雷两种状况:雷用1表示,非雷用0表示.则将当前状态用二维数组表示如下: 在右侧的二维数组中,很多都是0,即记录了很多没有意义的数据,因此,我们考虑使用稀疏数组进行存储结构的优化. 1.2 稀疏数组简介 当一个数组中的大

  • PHP在线生成二维码(google api)的实现代码详解

    通过google在线生成二维码的api在线生成二维码. 代码如下: 复制代码 代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> &l

  • Java二叉搜索树基础原理与实现方法详解

    本文实例讲述了Java二叉搜索树基础原理与实现方法.分享给大家供大家参考,具体如下: 前言:本文通过先通过了解一些二叉树基础知识,然后在转向学习二分搜索树. 1 树 1.1 树的定义 树(Tree)是n(n>=0)个节点的有限集.n=0时称为空树.在任意一颗非空树中: (1)有且仅有一个特定的称为根(Root)的节点: (2)当n>1时,其余节点可分为m(m>0)个互不相交的有限集T1.T2........Tn,其中每一个集合本身又是一棵树,并且称为根的子树. 此外,树的定义还需要强调以

  • Java二维数组简单定义与使用方法示例

    本文实例讲述了Java二维数组简单定义与使用方法.分享给大家供大家参考,具体如下: Java的二维数组是先创建一个一维数组,然后该数组的元素再引用另外一个一维数组.在使用二维数组的时候,通过两个中括号[]来访问每一层维度的引用,直到访问到最终的数据. public class MultiDimArray{ /** * @param args */ public static void main(String[] args) { int[][] arr = new int[3][]; arr[0]

  • Java二维数组实战案例

    本文实例讲述了Java二维数组.分享给大家供大家参考,具体如下: 一 点睛 1 每行的元素个数不同的二维数组 Java定义二维数组更加灵活,允许二维数组中的每行的元素个数不相等,这点与其他编程语言不同,例如下面这个二维数组,其中第1行有4个元素,第2行有3个元素,第3行有5个元素 int [][] num={ {1,2,3,4}, {1,2,3}, {1,2,3,4,5} }; 下面的语句是声明整型的二维数组num并分配空间,其中第1行4个元素,第2行3个元素,第3行5个元素 int [][]

  • Java二维数组与动态数组ArrayList类详解

    Java二维数组 Java 语言中提供的数组是用来存储固定大小的同类型元素. 1.二维数组初始化和声明 数组变量的声明,和创建数组可以用一条语句完成,如下所示: int a[][] = new int[2][3]; int[][] arr = {{1,2,3},{4,5,6},{7,8,9}}; 2.二维数组遍历 //遍历二维数组 public class Traverse_a_two_dimensional_array { public static void main(String[] ar

  • java二维数组指定不同长度实例方法

    我们知道二维数组,是在一维数组的基础上进行了维度的增加.那么在实际使用的过程中,有时候我们所需要的二维数组,它们其中的维度是不同的,这就需要我们手动的进行设置.下面我们就来一起探究,二维数组在改变维度长度大小的方法,并辅以实例进行代码展示. 1.二维数组的每个元素都是一个一维数组,这些数组不一定都是等长的.声明二维数组的时候可以只指定第一维大小,空缺出第二维大小,之后再指定不同长度的数组.但是注意,第一维大小不能空缺(不能只指定列数不指定行数). public class ArrayTest4

  • java二维数组基础知识详解

    目录 1. 查找 2. 顺序查找 3. 二分查找 4. 多维数组 4.1 二维数组 175 4.2 二维数组细节 5. 二维数组的使用方式 176 6. 二维数组的动态初始化 1.先声明:类型 数组名[][]; 再定义(开辟空间) 数组名 = new 类型[大小][大小] 2.动态初始化-列数不确定 178 7. 二维数组的静态初始化 179 8. 二维数组练习 180 8.1 int arr[][]={{4,6},{1,4,5,7},{-2}}; 遍历该二维数组,并得到和 1. 查找 1) 顺

随机推荐