当前位置:

首页 > 编程开发 > Java的实现:原始数组与稀疏数组的相互转换

Java的实现:原始数组与稀疏数组的相互转换

1、是什么?比如有一个11*11的五子棋盘,我们要用程序模拟,那肯定就是二维数组。然后用1表示黑子,2表示白子,假如现在棋盘上只有一个黑子一个白子,那么也就是这个二维数组中只有一个1,一个2,其他都是无意义并不代表任何棋子的0,如下:00000000000000010000000002000000000000000000……当一个数组中大部分元素是0时,或者为同一个值时,就可以用稀疏数组来保存该数组。为什么要这么做?因为可以节省空间。2、怎么用?记录原数组有几行几列,有多少个不同的值把具有不同值的元素的行

本文目录

    1、是什么?

    比如有一个 11 * 11 的五子棋盘,我们要用程序模拟,那肯定就是二维数组。然后用1表示黑子,2表示白子,假如现在棋盘上只有一个黑子一个白子,那么也就是这个二维数组中只有一个1,一个2,其他都是无意义并不代表任何棋子的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 2 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0
    ……

    当一个数组中大部分元素是0时,或者为同一个值时,就可以用稀疏数组来保存该数组。为什么要这么做?因为可以节省空间。

    2、怎么用?

    • 记录原数组有几行几列,有多少个不同的值

    • 把具有不同值的元素的行列及值记录在一个小规模数组中,这个小规模的数组就叫稀疏数组

    3、案例:

    现有如下的 6 * 7 的原始数组:

    0   0   0   22   0   0   15
    0   11  0   0    0   17   0
    0   0   0  -6    0   0    0
    0   0   0   0    0   39   0
    91  0   0   0    0   0    0
    0   0   28  0    0   0    0

    首先稀疏数组第一行第一列是记录元素数组有几行,第一行第二列是记录原始数组有几列,第一行第三列是记录原始数组有几个不同的值(除了0)。所以稀疏数组一行应该是:

    行    列    值
    6     7     8

    稀疏数组第二行开始,每行记录的是,原始数组中非0值所在的行、所在的列、值的大小。比如第二行要记录22在原始数组中的行、列、值,那么稀疏数组第二行就是:

    行    列    值
    0     3     22

    然后用此方法记录15、11、17、-6、39、91、28的相关信息,所以最终由该原始数组转化出来的稀疏数组就是:

    行    列    值
    6     7     8
    0     3     22
    0     6     15
    1     1     11
    1     5     17
    2     3     -6
    3     5     39
    4     0     91
    5     2     28

    这样就把一个 6 * 7 的数组变成了一个 9 * 3 的数组,达到了压缩的效果。

    4、原始数组与稀疏数组相互转换思路:

    原始数组转稀疏数组:

    • 遍历二维数组得到有效数组的个数count;

    • 根据count就可以创建稀疏数组      int[count + 1][3];

    • 将有效数组存入稀疏数组

    稀疏数组转原始数组:

    • 读取稀疏数组第一行,根据第一行数组可以知道原始数组有几行几列,然后创建原始数组;

    • 读取稀疏数组后几行的数组,赋值给原始数组即可

    5、代码实操:

    public class SparseArray {
        public static void main(String[] args){
            // 创建一个 11 * 11的原始数组
            int[][] arr1 = new int[11][11];
            arr1[1][2] = 1;
            arr1[2][3] = 2;
    
            // 原始数组转稀疏数组
            // 1. 遍历,得到非0数据的个数以及所在的行列
            int count = 0;
            Map map = new HashMap<>();
            for (int i = 0; i < arr1.length; i++) {
                for (int j = 0; j < arr1[i].length; j++) {
                    if (arr1[i][j] != 0){
                        count ++;
                        map.put(i+ "," + j, arr1[i][j]);
                    }
                }
            }
            // 2. 创建稀疏数组
            int[][] sparseArr = new int[count + 1][3];
            sparseArr[0][0] = arr1.length;
            sparseArr[0][1] = arr1[0].length;
            sparseArr[0][2] = count;
            // 3. 给稀疏数组赋值
            int row = 1;
            for (String key : map.keySet()){
                String[] ij = key.split(",");
                int i = Integer.parseInt(ij[0]);
                int j = Integer.parseInt(ij[1]);
                sparseArr[row][0] = i;
                sparseArr[row][1] = j;
                sparseArr[row][2] = map.get(key);
                row ++;
            }
            // 4. 遍历稀疏数组
            for (int i = 0; i < sparseArr.length; i++) {
                for (int j = 0; j < sparseArr[i].length; j++) {
                    System.out.print(sparseArr[i][j] + "   ");
                }
                System.out.println("\r\n");
            }
    
            // 稀疏数组恢复原始数组
            // 1. 根据第一行第一列第二列创建出原始数组
            int i = sparseArr[0][0];
            int j = sparseArr[0][1];
            int[][] arr2 = new int[i][j];
            // 2. 给原始数组赋值
            for (int k = 1; k < sparseArr.length; k++) {
                int x = sparseArr[k][0];
                int y = sparseArr[k][1];
                int val = sparseArr[k][2];
                arr2[x][y] = val;
            }
            // 3. 遍历转换的数组
            for (int a = 0; a < arr2.length; a++) {
                for (int b = 0; b < arr2[a].length; b++) {
                    System.out.print(arr2[a][b] + "   ");
                }
                System.out.println("\r\n");
            }
        }
    }

    上面的代码就实现了原始数组与稀疏数组的相互转换,灵活运用稀疏数组,可以节省运行内存,提高程序性能。

    本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系bd@zhengruan.com
    作者最新文章
    编程开发 Java
    上一篇: bobo
    相关文章 更多
    Yandex官网入口及网页搜索使用方法
    Yandex官网入口及网页搜索使用方法

    Yandex官网入口是https://www.yondex.net/,该平台支持多语言切换、智能搜索匹配、虚拟键盘变更及实时翻译,提供地图、图片、新闻、购物等垂直服务,并具备账户同步、隐私管理、个性化首页和云存储等功能。

    Java单元测试入门:使用JUnit 5编写第一个测试用例
    Java单元测试入门:使用JUnit 5编写第一个测试用例

    面向初学者的JUnit 5实用入门指南。从测试概念、Maven依赖配置,到手把手编写首个单元测试用例及断言验证,助你掌握Java单元测试的核心流程。

    Java变量未初始化报错解析:局部变量与成员变量默认值差异
    Java变量未初始化报错解析:局部变量与成员变量默认值差异

    深入解析Java中局部变量未初始化编译报错与成员变量自动赋予默认值的机制差异,涵盖JVM内存分配、编译期确定性赋值检查与实际排查修复方案。

    Java获取当前时间并格式化输出:DateTimeFormatter与SimpleDateFormat
    Java获取当前时间并格式化输出:DateTimeFormatter与SimpleDateFormat

    详细讲解在Java中获取当前系统时间并进行格式化输出的两种核心方案:基于Java 8全新日期时间API的DateTimeFormatter与传统遗留的SimpleDateFormat,包含完整代码示例、线程安全机制对比及生产选型建议。

    Java中final与static final常量的定义及初始化规则
    Java中final与static final常量的定义及初始化规则

    深入解析Java中final变量与static final常量的定义、内存语义、初始化时机及合法赋值路径,涵盖编译期常量优化与实战避坑指南。

    Java抽象方法与接口方法的区别及选型建议
    Java抽象方法与接口方法的区别及选型建议

    深入对比Java中抽象类抽象方法与接口方法的语法演进、设计意图及运行期差异,并提供清晰的架构选型决策流程与实战范例。

    Java实现HTTP请求与JSON解析的完整代码示例
    Java实现HTTP请求与JSON解析的完整代码示例

    本文提供Java标准库HttpClient发起HTTP GET/POST请求并结合Jackson进行JSON数据反序列化与序列化的完整代码示例与工程实践指南。

    Java递归出现StackOverflowError的原因分析及栈空间优化方案
    Java递归出现StackOverflowError的原因分析及栈空间优化方案

    详细分析Java递归调用出现StackOverflowError的原因,结合代码说明线程栈、栈帧和递归深度之间的关系,并介绍终止条件排查、迭代改写、减少栈帧开销以及通过-Xss调整JVM栈空间的方法。

    Java空指针异常(NPE)的代码排查与修复实例
    Java空指针异常(NPE)的代码排查与修复实例

    针对Java中常见的NullPointerException(NPE),本文从堆栈日志定位、典型代码触发场景、具体修复代码对比到防御体系进行系统讲解,提供实用且易上手的排查与修复方案。

    selenium上传文件教程本地文件路径设置方法
    selenium上传文件教程本地文件路径设置方法

    深入解析Selenium处理文件上传的技术细节,涵盖标准HTML控件的路径直接注入法与非标准控件的系统级模拟方案,提供Windows与Linux环境下的路径设置最佳实践及常见异常排查。

    查看更多
    精品专题 更多
    装机必备
    装机必备

    正软商城装机必备专区,精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件,帮助用户快速完成新电脑软件配置。

    Windows
    Windows

    正软商城Windows软件专区,汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件,提供软件介绍、系统要求、正版授权及购买下载服务。

    PDF教程
    PDF教程

    正软商城PDF教程频道提供PDF编辑、转换、合并、拆分、压缩及格式处理方法,同时介绍常用PDF软件和工具的使用技巧。

    Mac软件 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    Aperty macOS版
    Aperty macOS版
    macOS

    Aperty 是 Skylum 推出的 AI 人像修图软件,支持自然肤质修饰、瑕疵处理、面部与身体调整、预设及批量同步。

    WINDOWS 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    PixTV 网页版
    PixTV 网页版
    Windows

    PixTV 是一款在浏览器中使用的 AI 视觉内容创作平台,提供图片、视频、音频、文字生成、AI 分镜、局部重绘、提示词反推和无限画布等工具,适合短剧、漫剧、广告及社交媒体内容制作。