内容简介:近期刷题有一个新的体会,那就是以leetcode 565 为例,这题大意如下:一个长度为 n 的整形数组 A ,每个数的范围都在 0 到 n-1 以内,假设从数组的某个索引 i 开始,依次执行 A[i] 求值操作,将得到的数加入到集合 S 中,直到集合 S 出现重复元素为止,即中止运算。例如数组 [5,4,0,3,1,6,2] ,我们从 0 开始,依次执行求值操作,有:在上个例子中我们的 S 集合为 {5,6,2,0}。现在给定一个数组,我们要求出这个集合的最长长度。
近期刷题有一个新的体会,那就是 不要想着 pass 就完事了,得想办法将自己的运行时间提速
以leetcode 565 为例,这题大意如下:一个长度为 n 的整形数组 A ,每个数的范围都在 0 到 n-1 以内,假设从数组的某个索引 i 开始,依次执行 A[i] 求值操作,将得到的数加入到集合 S 中,直到集合 S 出现重复元素为止,即中止运算。例如数组 [5,4,0,3,1,6,2] ,我们从 0 开始,依次执行求值操作,有:
A[0]=5 -> A[5]=6 -> A[6]=2 -> A[2]=0 -x-> A[0]=5 复制代码
在上个例子中我们的 S 集合为 {5,6,2,0}。现在给定一个数组,我们要求出这个集合的最长长度。
刚开始看这题我感觉很容易啊,直接模拟不就完事了吗,遍历数组的每个值,将索引 i 作为起点并依次执行 A[i] 操作(计数当前的操作次数),当某次求值操作与起点 i 相同时则终止,最后取最大值即可,相应代码如下
func arrayNesting(nums []int) int { n := len(nums) if n <= 1 { return 1 } result := 0 for i := 0; i < n; i++ { s, current, tmpl := i, nums[i], 1 for current != s { current = nums[current] tmpl++ } result = maxValue(result, tmpl) } return result } func maxValue(a, b int) int { if a > b { return a } return b } 复制代码
这么写代码的话虽然也通过了,但是看了下耗时还是很不友好,居然是千毫秒级别
后面仔细想想,还是拿最初的数组 [5,4,0,3,1,6,2] 做例子,从索引 0 出发得到的集合为 [5,6,2,0] ,然而本质上如果从索引值为 2 5 或 6 出发的话得到的也是这个集合,因为它们始终凑成一个环。既然如此,那么我们可以**设置一个布尔数组,判断当前值如果之前已经出现在集合 S 内就不需要再重复计算,具体代码如下
func arrayNesting(nums []int) int { n := len(nums) if n <= 1 { return 1 } visited := []bool{} for i := 0; i < n; i++ { visited = append(visited, false) } result := 1 for i := 0; i < n; i++ { s, current, tmpl := i, nums[i], 1 visited[s] = true if visited[current] { continue } for current != s { current = nums[current] visited[current] = true tmpl++ } result = maxValue(result, tmpl) } return result } func maxValue(a, b int) int { if a > b { return a } return b } 复制代码
结果这个运行时间就比之前好多了,直接 20 毫秒
类似的操作还有 leetcode 240: 二维有序数组排序 ,题目大意是给定一个 m*n 的二维数组,从左到右以及从上到下都是有序的,如下面所示:
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30], ] 复制代码
现在就让你在这个矩阵内快速查找某个值,找到则返回 true ,找不到则返回 false,上述例子中搜索 5 则为 true,搜索 20 则为 false
首先最直观的思维就是遍历矩阵的每一行,判断当前要查找的值是否在当前行第 0 个元素和最后一个元素之间,如果是则对当前行的数组做二叉搜索
func searchMatrix(matrix [][]int, target int) bool { m := len(matrix) if m == 0 { return false } n := len(matrix[0]) if n == 0 { return false } result := false for _, row := range matrix { if target >= row[0] && target <= row[n-1] { result = binarySearch(row, n, target) } if result == true { return true } } return false } func binarySearch(row []int, n, target int) bool { left, right := 0, n-1 for left <= right { m := left + (right-left)/2 if row[m] == target { return true } else if target < row[m] { right = m - 1 } else { left = m + 1 } } return false } 复制代码
这样的效果虽然能通过,且时间也不算慢,但在此题运行时间的排名里只超过了 31.25% 的 golang coder,那么就说明了 O(m*log2(n)) 并不是这个算法的最优时间复杂度。另外理论上 m 要小于 n 才能算是比较好的算法,所以实际上我刚才的解法也忽视了分类讨论的情况:当 m < n 时按行遍历,当 m > n 时按列遍历
像我上面最初的想法,本质上只利用了从左到右有序这个性质,并没有充分利用从上到下有序这个性质。 从这个思维点出发,怎么样才能让这两个性质都一起用起来,从而加快速度?
还是拿上面的数组为例,比如我想搜索 6 ,我可以从最右上角的数字 15 出发,因为 15 在最右上角,结合矩阵的性质, 15 左边的元素都比 15 小(对应行), 15 下边的元素都比 15 大(对应列)
[ [1, 4, 7, 11, 15]<- [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30], ] 复制代码
那么 6 比 15 小,说明 6 不可能与 15 同列,于是我们数组的范围变为:
[ [1, 4, 7, 11]<- [2, 5, 8, 12] [3, 6, 9, 16] [10, 13, 14, 17] [18, 21, 23, 26] ] 复制代码
同理 6 比 11 和 7 小,所以数组的搜索范围为:
[ [1, 4, 7]<- [2, 5, 8] [3, 6, 9] [10, 13, 14] [18, 21, 23] ] [ [1, 4]<- [2, 5] [3, 6] [10, 13] [18, 21] ] 复制代码
继续看最右上角的数,这次 6 比 4 和 5 都大,说明 6 不可能跟 4 或 5 同行,所以搜索范围又缩小为:
[ [2, 5]<- [3, 6] [10, 13] [18, 21] ] [ [3, 6]<- [10, 13] [18, 21] ] 复制代码
现在我们找到 6 了,可以看到这个算法的时间复杂度最坏情况也是 O(m+n) ,比刚才有了一定的提升
func searchMatrix(matrix [][]int, target int) bool { m := len(matrix) if m == 0 { return false } n := len(matrix[0]) if n == 0 { return false } rightUp, currentRow, currentColumn := -1, 0, n-1 for currentRow >= 0 && currentRow < m && currentColumn >= 0 && currentColumn < n { rightUp = matrix[currentRow][currentColumn] if rightUp == target { return true } else if rightUp > target { currentColumn-- } else { currentRow++ } } return false } 复制代码
提交上去后,运行时间很美满
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
深入理解计算机系统(英文版·第2版)
[美] Randal E. Bryant、[美] David R. O'Hallaron / 机械工业出版社 / 2011-1 / 128.00元
本书是一本将计算机软件和硬件理论结合讲述的经典教程,内容覆盖计算机导论、体系结构和处理器设计等多门课程。本书的最大优点是为程序员描述计算机系统的实现细节,通过描述程序是如何映射到系统上,以及程序是如何执行的,使读者更好地理解程序的行为为什么是这样的,以及造成效率低下的原因。 相对于第1版,本版主要是反映了过去十年间硬件技术和编译器的变化,具体更新如下: 1. 对系统的介绍(特别是实际使......一起来看看 《深入理解计算机系统(英文版·第2版)》 这本书的介绍吧!