稀疏数组实现

博文主要是自己学习的笔记,供自己以后复习使用,
参考的主要教程是B站的
尚硅谷数据结构和算法

稀疏数组(sparse array)

实际需求:五子棋程序中的存盘退出和续上盘的功能

在这里插入图片描述

问题分析:

如果直接用二维数组,很多值是默认值0, 因此记录了很多没有意义的数据.->稀疏数组。
存盘:二维数组–>稀疏数组来–>持久化到磁盘中
续盘:将磁盘中的内容导入–>稀疏数组–>恢复二维数组

稀疏数组

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

稀疏数组的处理方法是:

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

举例:
在这里插入图片描述
在这里插入图片描述
第0行存储该二维数组有几行,几列,几个非空值
其余的行一次存储非空值的位置和值的大小

JAVA实现

public class SparseArray {
    public static void main(String[] args) {
        //创建一个原始的二维数组11*11
        //0:表示没有棋子,1:表示有棋子
        int chessArr1[][] = new int[11][11];
        chessArr1[1][2] = 1;
        chessArr1[2][3] = 2;
        chessArr1[4][5] = 3;

        //输出原始的二维数组
        System.out.println("原始的二维数组~~~~~~~~~~~~~~~~");

        for(int[] row :chessArr1){
            for(int data: row){
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }

        //将二维数组转为稀疏数组的思想
        //1、先遍历二维数组 得到非0数据的个数
        int sum = 0;
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (chessArr1[i][j] != 0) {
                    sum++;
                }
            }
        }
        //2.创建对应的稀疏数组
        int sparseArr[][] = new int[sum + 1][3];
        //给稀疏数组赋值
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = sum;

        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];
                }
            }
        }
        //输出稀疏数组的形式
        System.out.println();
        System.out.println("输出的稀疏数组为~~~~~~~~~~~~~~~~");
        for(int i = 0; i < sparseArr.length; i++) {
            System.out.printf("%d\t%d\t%d\t",sparseArr[i][0],sparseArr[i][1],sparseArr[i][2]);
            System.out.println();
        }

        //恢复成原始数组
        //1.构建
        int[][] chessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
        //2.赋值
        for (int i = 1; i < sparseArr.length; i++) {
            chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        System.out.println("恢复的二维数组~~~~~~~~~~~~~~~~");

        for(int[] row :chessArr2){
            for(int data: row){
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }

    }
}

结果如下:
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/439114.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

vue3+elementPlus:el-table-column表格列动态设置单元格颜色

:cell-style属性 //html<el-tableempty-text"暂无数据":data"datalist.table":max-height"height"row-key"id"border:cell-style"cellStyle"> <el-table>//js //动态设置单元格颜色 const cellStyle ({ row, c…

深入探索Transformer时代下的NLP革新

《基于GPT-3、ChatGPT、GPT-4等Transformer架构的自然语言处理》主要聚焦于如何使用Python编程语言以及深度学习框架如PyTorch和TensorFlow来构建、训练和调整用于自然语言处理任务的深度神经网络架构&#xff0c;特别是以Transformer为核心模型的架构。 书中详细介绍了Transf…

【Ubuntu 20.04 / 22.04 LTS】最新 esp-matter SDK 软件编译环境搭建步骤

仓库链接&#xff1a;esp-matter SDK官方软件说明&#xff1a;ESP Matter Programming Guide官方参考文档&#xff1a;使用 Matter-SDK 快速搭建 Matter 环境 (Linux) 环境要求 Ubuntu 20.04 或 Ubuntu22.04网络环境支持访问 Gihub 在安装 esp-matter SDK 软件编译环境之前&a…

day9 指针 函数封装

1&#xff1a;在主函数定义字符数组&#xff0c;在自定义函数中实现字符串比较 4 int my_strcmp(char *a,char *b);5 int main(int argc, const char *argv[])6 {7 //strcmp 函数比叫ascii码值大小8 char a[10]"hello";9 char b[10]"helloo";1…

windows环境下搭建minio分布式存储系统并通过nginx实现负载均衡

一、环境准备 windows环境下的minio可执行文件&#xff08;官网下载地址&#xff09;以及nginx&#xff08;官网下载地址&#xff09; 二、本地搭建minio集群 2.1、创建minio存储目录 如下图所示&#xff0c;在minioData目录下创建八个空文件夹 2.2、批处理文件启动mini…

义乌等保测评公司有哪些?用哪款堡垒机好?

对于义乌&#xff0c;相信大家都听过&#xff0c;也都知道&#xff0c;耳熟能详。这不有义乌小伙伴在问&#xff0c;义乌等保测评公司有哪些&#xff1f;用哪款堡垒机好&#xff1f;今天我们就来简单聊聊。 义乌等保测评公司有哪些&#xff1f; 目前浙江义乌本地暂未有正规等保…

ETL与抖音数据同步,让数据流动无阻

在当今数字化时代&#xff0c;数据的价值日益凸显&#xff0c;企业需要从各种渠道获取有关用户行为、市场趋势和竞争对手活动的数据。作为一家专注于数据集成和转换的领先平台&#xff0c;ETLCloud为企业提供了强大的数据同步和转换功能。而与此同时&#xff0c;抖音作为一款热…

多模态融合技术升级!新阶段2大融合模式取得最优性能

传统的多模态融合方法面临着模态表示不一致、灵活性不足等问题&#xff0c;难以适应日益复杂的实际需求。 而随着大模型等新技术的发展&#xff0c;研究者将这些新技术与传统的多模态融合相结合&#xff0c;提出了新阶段的融合模式&#xff0c;包括多模态大模型时代的新架构、…

构建高效Web应用:Flask、Django和FastAPI的全面对比

构建高效Web应用&#xff1a;Flask、Django和FastAPI的全面对比 介绍Flask简介快速入门路由和视图函数模板渲染数据库操作Flask项目实战 Django简介快速入门模型和数据库视图和模板表单处理Django项目实战 FastAPI简介快速入门路径操作和参数请求和响应依赖注入FastAPI项目实战…

基于协同过滤的旅游推荐系统设计与实现

基于协同过滤的旅游推荐系统设计与实现 在当今旅游业蓬勃发展的背景下&#xff0c;人们对于旅游体验的需求日益增加&#xff0c;如何为用户提供更加个性化、精准的旅游推荐成为了旅游行业的一个重要课题。为解决这一问题&#xff0c;我们设计并实现了一个基于协同过滤的旅游推…

苹果电脑专业的Mac垃圾清理工具CleanMyMac X4.14.7

CleanMyMac X是一款专业的Mac清理工具&#xff0c;它具有强大的功能和易用的界面&#xff0c;可以帮助用户快速清理Mac上的无用文件和垃圾&#xff0c;优化系统性能&#xff0c;提升电脑运行速度。 该软件的核心功能包括智能扫描与清理、应用程序管理、隐私保护和系统维护等。…

通用电气 IS220PTURH1BF 涡轮机输入/输出(输入/输出组件)

通用电气 IS220PTURH1BF 涡轮机输入/输出&#xff08;输入/输出组件&#xff09; 一个完整的根据工程的解决方案 通用电气具有丰厚经历的功用安全专家能够设计、履行和支撑您的整个安全体系——包括硬件、软件和使用工程&#xff0c;使您的系统泊车危险最小&#xff0c;一起满意…

计算机组成原理之机器:存储器之主存储器

计算机组成原理之机器&#xff1a;存储器 笔记来源&#xff1a;哈尔滨工业大学计算机组成原理&#xff08;哈工大刘宏伟&#xff09; Chapter3&#xff1a;存储器 3.1 概述 存储器可分哪些类型&#xff1f; 现代存储器的层次结构&#xff0c;为什么要分层&#xff1f; …

强化学习工具箱(Matlab)

1、Get Started 1.1、MDP环境下训练强化学习智能体 MDP环境如下图 每个圆圈代表一个状态每个状态都有上或下的选择智能体从状态 1 开始智能体接收的奖励值为图中状态转移的值训练目标是最大化累计奖励 &#xff08;1&#xff09;创建 MDP 环境 创建一个具有 8 个状态和 2 …

MVO-CNN-BiLSTM多输入分类预测|多元宇宙优化算法-卷积-双向长短期神经网络分类预测(Matlab)

目录 一、程序及算法内容介绍&#xff1a; 基本内容&#xff1a; 亮点与优势&#xff1a; 二、实际运行效果&#xff1a; 三、算法介绍&#xff1a; 四、完整程序下载&#xff1a; 一、程序及算法内容介绍&#xff1a; 基本内容&#xff1a; 本代码基于Matlab平台编译&am…

js【详解】原型 vs 原型链

原型 每个 class 都有显示原型 prototype每个实例都有隐式原型_proto_实例的_proto_指向对应 class 的 prototype 如下范例&#xff1a; class Student 创建了 实例 xialuo 获取属性 xialuo.name 或执行方法 xialuo.sayhi()时&#xff0c;先在自身属性和方法寻找&#xff0…

进程之舞:操作系统中的启动、状态转换与唤醒艺术

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua&#xff0c;在这里我会分享我的知识和经验。&#x…

【MOMO_Tips】批量将word转换为PDF格式

批量将word转换为PDF格式 1.打开文件–>选项–>自定义功能区–>开发工具–>确定 2.点开开发工具&#xff0c;选择第一个visual basic 3.进入页面后找到插入–>模块&#xff0c;就可以看到这样的画面之后将下列vba代码复制粘贴到模块中 Sub ConvertWordsToPd…

【Redis】Redis的应用场景

&#x1f4dd;个人主页&#xff1a;五敷有你 &#x1f525;系列专栏&#xff1a;Redis ⛺️稳中求进&#xff0c;晒太阳 Redis的应用场景&#xff1a; 限流 要求10s内只能访问一次 RequestMapping("xian")public String xianLiu(String sign){String sign1 …

LVGL在VScode中安装模拟器运行配置笔记教程

1、LVGL模拟器工程搭建 LVGL(Light and Versatile Graphics Library,轻巧而多功能的图形库)是一个免费的开放源代码图形库,它提供创建具有易于使用的图形元素,精美的视觉效果和低内存占用的嵌入式GUI所需的一切。本文主要讲述如何实现在VScode中实现LVGL模拟器环境的搭建运行。…