近期刷题有一个新的体会, 那就是不要想着 pass 就完事了, 得想办法将自己的运行时间提速
以 leetcode 565 https://leetcode.com/problems/array-nesting/ 为例, 这题大意如下: 一个长度为 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
- }
提交上去后, 运行时间很美满
来源: https://juejin.im/post/5bf01b60e51d451aa501f5cd