题解 | #在行列都排好序的矩阵中找指定的数#
在行列都排好序的矩阵中找指定的数
http://www.nowcoder.com/practice/b929be9dbbaa489a91afa3fec195c228
首先,如果直接采用遍历数组的方式会导致时间复杂度为O(M*N),但是题目要求时间复杂度为O(M+N),所以要从矩阵已经排好序这一点出发,假设从左往右,从上往下都为升序;如果左上角的数小于目标数,那么往右和往下都是往数值大的方向,但是有两个方向,不好操作;如果左下角的数小于目标数,那么往右是往数值大的唯一方向,可以操作。
第一步,比较左下角数值与目标值大小,左下角数值大的话,目标值应该往上找;左下角数值小的话,目标值应该往右找;
第二步,左下角的位置往上和右走一步,继续第一步;直至遍历斜角位置。
可以看出本算法是利用顺序排列,通过比较的方式来选择两个方向中的唯一方向,减少算法的时间复杂度。