数据结构和算法-原始数组转稀疏数组(一)|学习笔记

简介: 快速学习数据结构和算法-原始数组转稀疏数组(一)

开发者学堂课程【Go 语言核心编程 - 数据结构和算法:数据结构和算法-原始数组转稀疏数组(一)】学习笔记,与课程紧密联系,让用户快速学习知识。

课程地址:https://developer.aliyun.com/learning/course/627/detail/9829


数据结构和算法-原始数组转稀疏数组(一)

 

内容简介:

一、应用实例

二、代码实现

 

一、应用实例

看一个具体的案例,第一步使用稀疏数组来保存类似前面的二维数组,比如棋盘或者地图等等,第二步把稀疏数组存盘,把它存在文件里去,并且可以重新恢复原来的二维数组,

整体的思路分析如图所示:

image.png

这是一个二维数组,11乘11的,那么要把它做成一个稀疏数组的话,思路是这样的:

比如这是一个稀疏数组,就记录了1和2,比如1是一行,二列是一个1,然后2是第二行第三列,就记录下来了,当然了要做一个标准的稀疏数组,它应该还要记录这个值,就是它一共有11行11列,然后其他值应该是零,标志性输出稀疏数组,它首先进入一共有11行有11列,默认值为零,把它记录下来,但是,对于这个 Go 语言而言,这个11如果把它重新恢复成二维数组的话,这个11意义不是特别大,因为有个问题,就是它在进行定义一个数组的时候,必须把那个写死,所以要恢复的话,可能得想办法把它做成一个切片性质的,那就意义不大了,所以说,如果是公务员,这两个值就是行和列有多少个,意义不是特别大,但是也可以把它记录下来,按照一个标准的稀疏数组应该把它记录下来,这样子现在就来把它完成了。

 

二、代码实现

(1)二维数组代码实现

首先打开 VSCode ,然后新建一个章节称之为 chapter20 ,在其内新建一个文件夹称为 sparsearry ,再在其内新建一个文件称为 main.go ,并输入以下代码:

package main

import (

fmt

)

func main() {

//1.先创建一个原始数组

var chessMap [11][11]int

chessMap[1][2] = 1 //黑子

chessMap[2][3] = 2 //蓝子

//2.输出看看原始的数组

for _, v := range chessMap {

for _, v2 := range v {

fmt.Printf(%d\t, v2)

}

fmt.Println()

}

}

看原始数组长什么样子,打开 D 盘,找到刚才写的这段代码所在的目录 chapter20 ,然后取出数组,接下来运行一下上述代码,结果如下:

image.png

(2)转换成稀疏数组

可以看到当前这个二数组,长得就跟我们想的很像有一个1有一个2,那么这个时候发现这样不合理,因为如果原先按照这个方式去存盘,它一共有11乘以11个数据,规模比较大,那现在要把它转成稀疏数组,怎么把它转成一个稀疏数组?

显然事先并不知道有多少个有效数据那在 go 语言里面,只能使用切片,因为并不知道有一个1和2如果用切片应该怎么保存比较好?

最好的一种设计方式就是直接用一个结构体就可以了,需注意,结构体仍然是可以做成一个数组的因为在一个切片里面放有多个结构体实例,它就是一个结构体的一种切片那切片的本质还是一个数组,所以这个是没有问题的,这个就叫大家去想怎么做,这个就叫算法这个算法好像很神秘的样子,算法可以说是无处不在比如说将来在实现购物编程的时候,别人让你去把近十天前十个浏览的商品给我拍到上面去,你写一段代码,这个也叫算法只是有些算法,它是一些常规算法,都认同的一种算法,比如说语音识别算法比如像人工智能的图像识别、语音识别、图像识别,还有文字识别,那些是比较有名的算法都认同的有些算法是在工作实际开发中去解决一个小问题,设计的一个解决方案,也叫算法,那么算法怎么做?

//思路

//(1).遍历 chessMap ,如果我们发现有一个元素的值不为0,创建一个 node 结构体

//(2).将其放入到对应的切片即可

这时的问题在于结构体要怎么设计?显然这个结构体,至少应该有三个字段,一个是行,一个是列,输入以下代码:

type ValNode struct {

row int

col int

val int

}

(3)切片代码实现

结构体设计就好了,定好了过后,个切片就可以把它定下来,现在先做一个切片,输入以下代码:

var sparseArr []ValNode

for i, v := range chessMap {

for j, v2 := range v {

if v2 != 0 {

//创建一个 ValNode 值结点

valNode = ValNode[

row : i,

col : j,

val : v2,

}

}

}

}

相关文章
|
6月前
|
设计模式 算法 Java
【数据结构和算法】确定两个字符串是否接近
这是力扣的1657题,难度为中等,解题方案有很多种,本文讲解我认为最奇妙的一种。复杂度分析:时间复杂度:O(max⁡{n1,n2}+Clog⁡C),其中 n1 和 n2 分别是字符串 word1 和 word2 的长度,C=26 是字符集大小。空间复杂度:O(C)。
72 1
|
6月前
|
设计模式 算法 Java
【数据结构和算法】除自身以外数组的乘积
给你一个整数数组nums,返回数组answer,其中answer[i]等于nums中除nums[i]之外其余各元素的乘积。题目数据保证数组nums之中任意元素的全部前缀元素和后缀的乘积都在32 位整数范围内。请不要使用除法,且在O(n)时间复杂度内完成此题。
52 1
|
6月前
|
算法
【数据结构】哈希经典应用:位图——[深度解析](8)
【数据结构】哈希经典应用:位图——[深度解析](8)
|
6月前
|
存储 算法 搜索推荐
【数据结构】哈希经典应用:布隆过滤器(哈希+位图)——[深度解析](9)
【数据结构】哈希经典应用:布隆过滤器(哈希+位图)——[深度解析](9)
|
6月前
|
存储 算法 NoSQL
【C/C++ 数据结构】稀疏矩阵解析:从原理到 C++ 实现 指南
【C/C++ 数据结构】稀疏矩阵解析:从原理到 C++ 实现 指南
299 0
|
6月前
|
存储 设计模式 算法
【数据结构和算法】找出两数组的不同
这是力扣的 2215 题,难度为简单,解题方案有很多种,本文讲解我认为最奇妙的一种。给你两个下标从0开始的整数数组nums1和nums2,请你返回一个长度为2的列表answer,其中: answer[0]是nums1中所有不存在于nums2中的不同整数组成的列表。 answer[1]是nums2中所有不存在于nums1中的不同整数组成的列表。 注意:列表中的整数可以按任意顺序返回。
88 1
|
算法 测试技术 C#
C++算法:找出数组的第 K 大和原理及实现
C++算法:找出数组的第 K 大和原理及实现
|
存储 Java
(一)Java数据结构之稀疏数组
稀疏数组(sparse array)是一种只为数组中的非零元素分配内存的特殊类型数组,分为三列: 1.行下标 2.列下标 3.值 第一行为总行数、总列数、值的个数,其他行存储了非零元素的下标和值。
60 0
|
存储 算法
一篇文章让你彻底理解数组及其扩展的数据结构,快速转置算法等,千字超详细总结!
数组 本章主要介绍数组基本概念及其扩展,二维数组的特殊矩阵:对称矩阵、三角矩阵、稀疏矩阵、十字链表等存储解耦;然后介绍并实现了稀疏矩阵的快速转置算法。 可以转载,但请声明源链接:文章源链接justin3go.com(有些latex公式某些平台不能渲染可查看这个网站)
122 0
|
Java 定位技术
减小程序规模!稀疏数组Sparsearray,数据结构二维数组与稀疏数组转换,Java实现
减小程序规模!稀疏数组Sparsearray,数据结构二维数组与稀疏数组转换,Java实现
120 1
减小程序规模!稀疏数组Sparsearray,数据结构二维数组与稀疏数组转换,Java实现