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

目录
  • 1.稀疏数组引入
    • 1.1 使用场景
    • 1.2 稀疏数组简介
  • 2.稀疏数组的实现
    • 2.1 案例概述
    • 2.2 思路分析
    • 2.3 代码实现

1.稀疏数组引入

1.1 使用场景

笔者在课程设计中曾写过一个扫雷小游戏,为了便于讲解,我们来做个简化(实际比这个复杂),只考虑当前位置有雷与无雷两种状况:雷用1表示,非雷用0表示。则将当前状态用二维数组表示如下:

在右侧的二维数组中,很多都是0,即记录了很多没有意义的数据,因此,我们考虑使用稀疏数组进行存储结构的优化。

1.2 稀疏数组简介

当一个数组中的大部分元素都是0(或者为相同的某一值),可以考虑使用稀疏数组来优化保存。

而稀疏数组的基本处理方式为:

记录数组有几行几列,有几个有效值;

把有效值的元素的行、列及值记录在一个小规模的数组中,从而缩小程序的规模。

例如上述的二维数组用稀疏数组表示,可以创建一个n*3列的稀疏数组。其中,n为有效值个数加1,第一行用于存储二维数组的行数、列数及有效值的个数,便于恢复二维数组时使用。

而从第二行开始后的每一行,都记录某个有效值的所在行、列索引与值。

上述二维数组用稀疏数组表示如下:

稀疏数组的第n行 row col val
0 10 10 8
1 0 4 1
2 0 8 1
3 1 5 1
4 1 7 1
5 4 8 1
6 5 5 1
7 7 2 1
8 8 7 1

以索引0那行,10 10 8为例:表示原二维数组有10行10列,共有8个有效值。

以索引1那行,0 4 1为例:即第一个有效值在原数组的第0行第4列(索引为0和4),值为1,以此类推…

2.稀疏数组的实现

2.1 案例概述

1.使用稀疏数组来保存前面1.1样例中的二维数组(见下图);

2.可以由稀疏数组恢复成二维数组。

2.2 思路分析

二维数组转稀疏数组:

遍历原始的二维数组,得到有效数据的个数 amount;

根据 amount 可以创建稀疏数组 sparseArray[amount+1][3];

将二维数组中的有效值存入稀疏数组中。

稀疏数组恢复二维数组:

先读取稀疏数组的第一行,根据第一行的数据,创建原始二维数组;

读取第二行及以后行的数据,按照每行的行、列、值恢复有效值,录入二维数组中。

2.3 代码实现

根据如上思路,逐步实现稀疏数组,详情可见代码注释

参考代码:

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * 二维数组转稀疏数组、稀疏数组还原二维数组的实现
 */
public class SparseArray {

    public static void main(String[] args) {
        //先创建原始二维数组
        int[][] originalArray = new int[10][10];
        originalArray[0][4] = 1;
        originalArray[0][8] = 1;
        originalArray[1][5] = 1;
        originalArray[1][7] = 1;
        originalArray[4][8] = 1;
        originalArray[5][5] = 1;
        originalArray[7][2] = 1;
        originalArray[8][7] = 1;
        //输出原始的二维数组
        System.out.println("原始的二维数组:");
        for (int[] row: originalArray) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }

        //将二维数组转成稀疏数组
        //1.遍历二维数组,得到非0的有效数据的个数
        int amount = 0;
        for (int i = 0; i < originalArray.length; i++) {
            for (int j = 0; j < originalArray[i].length; j++) {
                if (originalArray[i][j] != 0){
                    amount++;
                }
            }
        }
        System.out.println("amount = " + amount);
        //2.创建对应的稀疏数组 sparseArray[amount+1][3], 并初始化稀疏数组第一行的数据
        //第一行第一列: 原数组的行数   第一行第二列: 原数组的列数  第一行第三列: 原数组的有效数据个数
        int[][] sparseArray = new int[amount + 1][3];
        sparseArray[0][0] = 10;
        sparseArray[0][1] = 10;
        sparseArray[0][2] = amount;
        //3.遍历二维数组,将非0值存储进稀疏数组
        int count = 0; //用于记录是第几个非零数据
        for (int i = 0; i < originalArray.length; i++) {
            for (int j = 0; j < originalArray[i].length; j++) {
                if (originalArray[i][j] != 0){
                    count++;
                    sparseArray[count][0] = i; //记录所在行
                    sparseArray[count][1] = j; //记录所在列
                    sparseArray[count][2] = originalArray[i][j]; //记录值
                }
            }
        }
        //输出稀疏数组
        System.out.println("稀疏数组:");
        for (int i = 0; i < sparseArray.length; i++) {
                System.out.printf("%d\t%d\t%d\n", sparseArray[i][0], sparseArray[i][1], sparseArray[i][2]);
        }

        //将稀疏数组恢复成为二维数组
        //1.根据稀疏数组的第一行初始化二维数组
        int[][] recoveredArray = new int[sparseArray[0][0]][sparseArray[0][1]];
        //2.读取稀疏数组的后面行数据,赋值给原始二维数组
        for (int i = 1; i < sparseArray.length; i++) {
            recoveredArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }
        //输出二维数组
        System.out.println("恢复后的二维数组:");
        for (int[] row: recoveredArray) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
    }
}

运行结果:

原始的二维数组:
0    0    0    0    1    0    0    0    1    0    
0    0    0    0    0    1    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    1    0    
0    0    0    0    0    1    0    0    0    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    0    0    0    1    0    0    
0    0    0    0    0    0    0    0    0    0    
amount = 8
稀疏数组:
10    10    8
0    4    1
0    8    1
1    5    1
1    7    1
4    8    1
5    5    1
7    2    1
8    7    1
恢复后的二维数组:
0    0    0    0    1    0    0    0    1    0    
0    0    0    0    0    1    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    1    0    
0    0    0    0    0    1    0    0    0    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    0    0    0    1    0    0    
0    0    0    0    0    0    0    0    0    0

比对结果如下:

经过比较,恢复后的二维数组与原二维数组保持一致!

分析可知:原二维数组需要的空间为:10 * 10 *(int),而稀疏数组只需要 9 * 3 * (int),相对节省了73(int)的空间!

以上就是Java数据结构之稀疏数组的实现与应用的详细内容,更多关于Java稀疏数组的资料请关注我们其它相关文章!

(0)

相关推荐

  • Java postgresql数组字段类型处理方法详解

    在实际开发中遇到postgresql中定义的数组字段,下面解决两个问题,如何定义数组字段的默认值为空格数组,以及如何再java实体类中直接使用数组对象接受数据或把数据存入数据库. 1.在postgresql中定义数组对象及默认值 以字符串你数组为例: 比如一个字段用于存储多张图片的url,可以使用一下sql定义 pictures _varchar NOT NUll default ARRAY[]::character varying[] 2.实体类存入数组到数据库并接受数据库的数组数据 直接定义

  • Java C++题解leetcode1441用栈操作构建数组示例

    目录 题目要求 思路:模拟[双指针] Java C++ Rust 题目要求 思路:模拟[双指针] 按题意模拟即可: 一个指针cur依次指向target中的每个元素,另一个指针i依次指向1∼n的数字: 对i所指向的每个数字进行Push操作,然后判断当前数字与target[cur]是否相等: 相等则判断下一个数字,同时将cur指向下一个元素: 否则需进行Pop操作. 过程中需注意cur的越界,当其越界则target构造完毕. Java class Solution { public List<Str

  • Java中如何将 int[] 数组转换为 ArrayList(list)

    目录 Java中数组转List的四种方式 第一种方式(未必最佳):使用ArrayList.asList(strArray) 第二种方法(支持增删查改): 第三种方式(通过集合工具类Collections.addAll()方法(最高效)) 第四种方式通过JDK8的Stream流将3总基本类型数组转为List java数组转list误区 一.不能把基本数据类型转化为列表 二.asList方法返回的是数组的一个视图 下面介绍下Java中如何将 int[] 数组转换为 List(ArrayList) 前

  • Java C++题解leetcode915分割数组示例

    目录 题目要求 思路一:两次遍历 Java C++ Rust 思路二:一次遍历 Java C++ Rust 题目要求 题目链接 思路一:两次遍历 题目的意思也就是左半边数组的最大值小于等于右半边数组的最小值,那么就找这个分界点就好: 首先从后向前遍历,找[i,n−1]里最小的值: 然后从前向后遍历,找[0,i]里最大的值: 然后找满足max[i]<=min[i+1]的分割点i: 可以将2.3两步结合为一步完成,由于iii从前向后不断增大,所以用后面(较大)的值覆盖更新之前的值. 找到分界点的索引

  • 关于Java SE数组的深入理解

    目录 1.数组的基本概念 1.1 我们为什么需要数组? 1.2 数组的创建与初始化 1.3 数组的使用 1.4 数组的遍历 2.引用类型数组的深入讲解 2.1 简单了解 JVM 的内存分布 2.2 基本类型变量与引用类型变量的区别 2.3 通过方法更深刻理解引用变量 2.4 数组作为函数返回值 3.二维数组 3.1 二维数组的概念和内存布局 3.2 二维数组的定义和初始化 3.3 二维数组遍历 3.4 不规则的二维数组 总结 1.数组的基本概念 1.1 我们为什么需要数组? 假设说我们要存每个同

  • Java中数组的常见操作合集

    目录 数组的常见操作 数组越界异常 数组空指针异常 数组遍历 数组获取最大值元素 数组反转 数组作为方法参数和返回值 数组作为方法参数 数组作为方法返回值 数组的常见操作 数组越界异常 public static void main(String[] args) { int[] array = {15, 25, 35}; System.out.println(array[0]); //15 System.out.println(array[1]); // 25 System.out.printl

  • Java数组队列及环形数组队列超详细讲解

    目录 一.队列 1.基本介绍 2.示意图 3.队列的特点 二.数组模拟队列 1.数组队列初始化 2.判断方法 3.增删改查的方法 4.注意 三.数组模拟环形队列 1.初始化 2.判断方法 3.增删改查的方法 一.队列 1.基本介绍 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表.进行插入操作的端称为队尾,进行删除操作的端称为队头. 2.示意图 3.队列的特点 先进先出: 在队列中插入一

  • Java数组(Array)最全汇总(中篇)

    目录 前言 本章学习要点 Java二维数组详解 创建二维数组 初始化二维数组 例 1 例 2 获取全部元素 例 3 例 4 获取整行元素 例 5 获取整列元素 例 6 Java不规则数组 Java数组也是一种数据类型 Java中到底有没有多维数组(长篇神文)? 前言 本章是关于Java数组的最全汇总,本篇为汇总中篇,主要讲了二维数组和不规则的数组的相关内容. 数组是最常见的一种数据结构,它是相同类型的用一个标识符封装到一起的基本类型数据序列或者对象序列. 数组使用一个统一的数组名和不同的下标来唯

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

    目录 一.稀疏数组 1.什么是稀疏数组 2.图示 3.稀疏数组的表达方式 二.二维数组→稀疏数组 三.稀疏数组→二维数组 一.稀疏数组 1.什么是稀疏数组 当一个数组中大部分元素为0,或者为同一个值的数组时,可以用稀疏数组来保存该数组.稀疏数组,记录一共有几行几列,有多少个不为零的值或相同的值. 简单来说就是将大规模的数组缩小成小规模的数据,从而减少空间浪费. 2.图示 上面的图示中,左侧是二维数组,右侧是稀疏数组,将二维数组转成稀疏数组,明显的可以看出空间减少了,可以有效的节约空间,提高效率.

  • Java中将 int[] 数组 转换为 List分享

    目录 前言 为什么不能用 Arrays 的 asList 方法将 int[] 装换成 ArrayList 使用stream进行转换(jdk8 推荐) 遍历数组,逐个加入元素到List中 前言 说起数组转换成 ArrayList,很多同学第一反应就是遍历数组,将元素逐个添加到 ArrayList 中,但是这个看着就lower,一般不会这么答. 所以马上就会想到Arrays工具类的 asList 方法,如果你这么答,那么恭喜你,答错入坑. 为什么不能用 Arrays 的 asList 方法将 int

  • Java之数组在指定位置插入元素实现

    1.假设在已知数组中在指定位置添加一个元素,那么在这位置的数据元素就会被替换掉. 代码: public class InsertArray { public static void main(String[] args) { int index = 2; int value = 5; int[] array = new int[]{1,2,3,4}; array[index] = value; System.out.println(Arrays.toString(array)); } } 测试结

  • java如何将int数组转化为Integer数组

    目录 将int数组转化为Integer数组 Java int和Integer互转原理 Java Integer.int 与 new Integer() Integer.valueOf() new Integer() 为什么 Java 9 不建议使用 new Integer 了? int 与 integer 相互转换及区别 将int数组转化为Integer数组 这里使用java8的stream来进行转化,详细步骤如下所示: //初始化int数组 int[] nums = {1,2,3,4,5,6}

  • 浅谈Java当作数组的几个应用场景

    目录 前言 1.保存数据 2.. 参数传基本数据类型 3.. 参数传数组类型(引用数据类型) 4. 作为函数的返回值 总结 前言 对于数组,在C语言中就有过学习,但是,并没有怎么进行总结过,所以,笔者在Java中,对数组的几个简单的应用场景进行总结一下: 1.保存数据 public static void main(String[] args) { int[] array = {1, 2, 3}; for(int i = 0; i < array.length; ++i){ System.out

  • 计算Java数组长度函数的方法以及代码分析

    Java 中的数组可以包含多个元素,具体取决于对象的创建方式.为了让用户执行不同的操作,必须知道数组的长度. 数组长度属性:如何求出数组的长度? 为了获得 Java 数组长度,我们需要使用“数组长度属性”,如下例所示: /** * An Example to get the Array Length is Java */ public class ArrayLengthJava { public static void main(String[] args) { String[] myArray

  • Java 从json提取数组并转换为list的操作方法

    目录 Java 从json提取数组并转换为list Java单个对象和List对象转换成Json,Json转List (一)使用单个对象转换JSON对象 (二)多个对象存到List,再转换成JSON (三)json的list对象转List对象 Java 从json提取数组并转换为list 这里ret表示json字符串原文 // 解析为JSONObject JSONObject jsonObject = JSONObject.parseObject(ret); // 提取出JSONArray JS

随机推荐