题解 | #在行列都排好序的矩阵中找指定的数#

在行列都排好序的矩阵中找指定的数

http://www.nowcoder.com/practice/b929be9dbbaa489a91afa3fec195c228

首先,如果直接采用遍历数组的方式会导致时间复杂度为O(M*N),但是题目要求时间复杂度为O(M+N),所以要从矩阵已经排好序这一点出发,假设从左往右,从上往下都为升序;如果左上角的数小于目标数,那么往右和往下都是往数值大的方向,但是有两个方向,不好操作;如果左下角的数小于目标数,那么往右是往数值大的唯一方向,可以操作。
第一步,比较左下角数值与目标值大小,左下角数值大的话,目标值应该往上找;左下角数值小的话,目标值应该往右找;
第二步,左下角的位置往上和右走一步,继续第一步;直至遍历斜角位置。

可以看出本算法是利用顺序排列,通过比较的方式来选择两个方向中的唯一方向,减少算法的时间复杂度。

全部评论

相关推荐

10-30 22:18
已编辑
毛坦厂中学 C++
点赞 评论 收藏
分享
沉淀一会:**圣经 1.同学你面试评价不错,概率很大,请耐心等待;2.你的排名比较靠前,不要担心,耐心等待;3.问题不大,正在审批,不要着急签其他公司,等等我们!4.预计9月中下旬,安心过节;5.下周会有结果,请耐心等待下;6.可能国庆节前后,一有结果我马上通知你;7.预计10月中旬,再坚持一下;8.正在走流程,就这两天了;9.同学,结果我也不知道,你如果查到了也告诉我一声;10.同学你出线不明朗,建议签其他公司保底!11.同学你找了哪些公司,我也在找工作。
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务