首页
关于
留言
接口
搜索
首页
登录
登录
搜索
KAKA 梦很美
累计撰写
47
篇文章
累计收到
0
条评论
首页
栏目
首页
登录
页面
首页
关于
留言
接口
包含标签 【算法】 的文章
置顶
数据结构与算法之稀疏数组
概念 当一个数组中存储了大量为0或者大量相同的数时, 为了缩小程序的规模, 我们可以使用稀疏数组来保存该数组。 处理方式是 通过记录数组一共有几行几列, 有多少个不同的值, 把具有不同值的元素的 行列值 记录在一个小规模数组(稀疏数组)中, 从而缩小程序的规模。 如果不太好理解,这里就举个最经典的五子棋场景。在编写一个五子棋的程序当中,要实现存盘退出和续上盘的功能。如下图所示: 存在一个棋盘, 退出保存的时候应该怎么存储呢? 使用一个二维数组, 1表示红棋, 2表示黑棋, 0表示没有下过的棋。 因为该二维数组的大部分值都是默认的0, 因此记录了很多没有意义的数据, 这个时候就可以使用到 稀疏数组。 实现思路 步骤一 创建二维数组作为源数据, 我们看下源数据效果: 步骤二 遍历原始的二维数组, 将源数据中的有效数据转换为稀疏数组, 并把总行数、总列数和默认值也作为一个元素写入到稀疏数组第一个元素位置。可以看到, 实际有效数据有7个, 但是会产生8个元素, 用来记录总行总列。 步骤三 将稀疏数组复原为源数据, 先单独处理第一行, 创建原始的默认二维数组, 然后再读取稀疏数组中的其他行数据并赋值给二维数组即可。 废话不多说, 直接上代码(Go语言编写) package main import ( "fmt" ) /******* 稀疏数组 - 五子棋案例 *******/ const ( ROW = 11 COL = 11 ) var ( classmap [ROW][COL]int ) type nodeval struct { row int col int val interface{} } func main() { // 输出原始数据 originalData() // 转换为稀疏数组存档 sparsearray := transformationSparseArrayStorage() // 转换为原始数据 transformationOriginalData(sparsearray) } // 原始数据 func originalData() { classmap[1][3] = 2 classmap[2][3] = 1 classmap[5][2] = 1 classmap[6][8] = 2 classmap[7][3] = 1 classmap[4][5] = 1 classmap[6][6] = 2 // 查看数据 for _, v := range classmap { for _, v1 := range v { fmt.Printf("%d\t", v1) } fmt.Println() // 换行输出, 避免影响数据显示 } // 输出: /** 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 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 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 2 0 0 0 0 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 0 0 0 0 0 0 0 0 0 0 */ } // 转换为稀疏数组存档 func transformationSparseArrayStorage() []nodeval { // 转为稀疏数组 (这里使用切片实现) var sparsearray []nodeval // 创建数据模型 sparsearray = append(sparsearray, nodeval{ row: ROW, col: COL, val: 0, }) // 存档 for row, val := range classmap { for col, val1 := range val { if val1 == 0 { continue } // 加入到切片 sparsearray = append(sparsearray, nodeval{ row: row, col: col, val: val1, }) } } fmt.Println(sparsearray) // 此数据可存档入文件、缓存、数据库等, 输出: [{11 11 0} {1 3 2} {2 3 1} {4 5 1} {5 2 1} {6 6 2} {6 8 2} {7 3 1}] return sparsearray } // 转换为原始数据 func transformationOriginalData(sparsearray []nodeval) { var arr [][]int for key, nv := range sparsearray { var v int switch nv.val.(type) { case int: v = nv.val.(int) default: } if key == 0 { // 制作原始表格初始数据 for i := 0; i < nv.row; i++ { var temp []int for j := 0; j < nv.col; j++ { temp = append(temp, v) } arr = append(arr, temp) } // fmt.Println(arr) /** [ [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 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 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 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 0] ] */ } else { // 棋盘数组内容赋值 arr[nv.row][nv.col] = v } } // 输出数据 for _, v := range arr { for _, v1 := range v { fmt.Printf("%d\t", v1) } fmt.Println() // 换行输出, 避免影响数据显示 } /** 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 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 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 2 0 0 0 0 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 0 0 0 0 0 0 0 0 0 0 */ }
2023年-3月-1日
204 阅读
0 评论
基础原理
2023-1-12
数据结构与算法之冒泡排序
概念 冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。 原理 比较两个相邻的元素,将值大的元素交换到右边。如果遇到相等的值不进行交换,那这种排序方式是稳定的排序方式。 思路 依次比较相邻的两个数,将比较小的数放在前面,比较大的数放在后面 1) 比较第1和第2个数,将小数放在前面,将大数放在后面。 2) 比较第2和第3个数,将小数放在前面,将大数放在后面。 ...依此类推 3) 当比较到第一轮最后两个数时候,将小数放在前面,将大数放在后面;其中最后一个数肯定是整个数组中的最大数,所以在接下来的轮次中是不需要参与比较的。 4) 在上面一轮比较完成后,需要重复如上步骤,每一轮比较次数依次减少,并且每一轮过后都会有一个不需要参与下轮比较的值,直至全部排序完成。 图解冒泡排序 需要参与冒泡排序的数组: [24, 0, 300, 69, 80, 4, 293, 57, 13] 算法分析可以看到: 逻辑处理: N个数字要排序完成,总共进行 N-1 轮次排序,每一次的排序次数为(N-i)次。所以可以用双重循环语句,外层控制循环总轮次,内层控制每一轮的循环次数。 规则原理: 每进行一轮次排序,就会少比较一次,因为每进行一轮排序都会找出一个较大值。如上例: 第一轮比较之后,排在最后的一个数一定是最大的一个数,第二趟排序的时候,只需要比较除了最后一个数以外的其他的数,同样也能找出一个最大的数排在参与第二轮比较的数后面,第三轮比较的时候,只需要比较除了最后两个数以外的其他的数,以此类推…… 也就是说,每进行一轮比较,每一轮少比较一次,一定程度上减少了算法的量。 时间复杂度: (1) 如果我们的数据正序,只需要走一轮即可完成排序。所需的比较次数C和记录移动次数M均达到最小值,即:Cmin=n-1; Mmin=0; 所以,冒泡排序最好的时间复杂度为O(n)。 (2) 如果很不幸我们的数据是反序的,则需要进行n-1轮次排序。每轮次排序要进行n-i次比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值。 冒泡排序总的平均时间复杂度为:O(n^2) [n的平方] , 时间复杂度和数据状况无关。 接下来用 Go 实现冒泡排序算法代码 package main import "fmt" /******* 冒泡排序法 *******/ func main() { var arr = [9]int{24, 0, 300, 69, 80, 4, 293, 57, 13} for j := 0; j < len(arr) - 1; j++ { var oldArr = arr var nextTotalLen = len(arr) - j - 1 for i := 0; i < len(arr); i++ { if i < nextTotalLen { var nextKey = i + 1 if arr[i] > arr[nextKey] { // 前面值大于后面值时, 位置置换 var nextVal = arr[i] arr[i] = arr[nextKey] arr[nextKey] = nextVal } } } // 值完全相同则不需要继续循环下去了 if oldArr == arr { break } } fmt.Println(arr) /** 输出: [0 4 13 24 57 69 80 293 300] */ }
2023年-1月-12日
201 阅读
0 评论
基础原理