从搜索排序二维数组到搜索有向图思维 2020-07-24(未允禁转)

9_SooHyun · · 277 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

本博客源于对leetcode74和leetcode240搜索二维矩阵的总结

问题

74. 搜索二维矩阵
编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
也就是说,矩阵是按从左到右,从上到下递增的

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

240. 搜索二维矩阵 II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性:
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
这题就复杂一点,顺序是局部的、穿插的

[
  [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]
]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/search-a-2d-matrix-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

对于这两个题,有两种解决思路:

  • 1.利于数据的原始有序排序整个矩阵,降维至有序一维数组,然后使用二分查找。对于题74,其实已经不需要再怎么排序了;对于题240,局部有序是吧,来个归并,时间复杂度O(m*n)

  • 2.这个思路比较清奇,对两个问题都适用。对于这种内部有序的矩阵,其4个顶点中,左上角永远是最小的,右下角永远是最大的,而右上角和左下角则厉害了,是比一侧大又比一侧小的,像极了二叉搜索树的根有没有。以右上角为例,它总比横排的元素大,而比纵排的元素小。那么我们从它开始进来搜索的话,就可以像搜索一棵二叉搜索树那样,比它大就走下面,比它小就走左边,这样只需要走一条路径就可以确定有没有目标元素。

注意,这样形成的搜索树并不是严格的二叉搜索树,因为这棵树的左子树和右子树没有严格的界限;实际上,从更深入更本质的角度看待它,它就是一个【有序有向图结构】,这两个题目实际上是对一个有向图形的搜索,应该推广到这样的层面去

以下提供golang通解

func searchMatrix(matrix [][]int, target int) bool {
    r := len(matrix)
    if r == 0 {
        return false
    }

    c := len(matrix[0])
    if c == 0 {
        return false
    }

    var i, j, ele int
    i, j = 0, c - 1
    for (0 <= i && i < r && 0 <= j && j < c) {
        ele = matrix[i][j]
        if ele == target {
            return true
        }else if ele > target {
            j --
        }else {
            i ++
        }
    }
    return false
}

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:9_SooHyun

查看原文:从搜索排序二维数组到搜索有向图思维 2020-07-24(未允禁转)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

277 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传