X

LEETCODE 240. Search a 2D Matrix II 解题思路分析

题目大意:

搜索二维矩阵 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] ]

给定 target = 5,返回 true

给定 target = 20,返回 false


如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=240

解题思路分析:

这是一道非常经典的有序矩阵二分查找问题,由于矩阵上每行每列都已升序排序,那么我们可以从左下角开始搜索,如果当前数值等于target,直接返回true。如果大于target,那么我们需要减小当前数字,即将当前行减一,反之如果小于target,我们需要加大当前数字,那么可以将当前列加一,直到找到target为止。如果行或者列超出数组范围仍没找到,返回false。

实现代码:

public boolean searchMatrix(int[][] matrix, int target) {
    // 初始点为左下角
    int row=matrix.length-1;
    int col=0;
    // 当坐标在矩阵范围内时,查找target
    while(row>=0&&col<matrix[0].length){
        // 如果当前数字等于target,返回true
        if(matrix[row][col]==target) return true;
        // 如果当前数字大于target,行减一
        if(matrix[row][col]>target) row--;
        // 如果当前数字小于target,列加一
        else col++;
    }
    return false;
}

本题解法执行时间为5ms。

Runtime: 5 ms, faster than 99.96% of Java online submissions for Search a 2D Matrix II.

Memory Usage: 50.3 MB, less than 5.66% of Java online submissions for Search a 2D Matrix II.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-240-search-a-2d-matrix-ii-解题思路分析/
Categories: leetcode
kwantong: