AI工具人
提示词工程师

Leetcode 74. Search a 2D Matrix

题目链接:Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
* Integers in each row are sorted from left to right.
* The first integer of each row is greater than the last integer of the previous row.

  这道题很简单,为此专门写篇博客其实算博客凑数了。给你一个每一行每一列都是增序,且每一行第一个数都大于上一行末尾数的矩阵,让你判断某个数在这个矩阵中是否存在。

  假设矩阵是mn,扫一遍的时间复杂度就是O(mn),题目中给出的这么特殊的矩阵,时间复杂度可以降到O(m+n),具体代码如下,写的比较挫。

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0)
            return false;
        int x = matrix.length;
        int y = matrix[0].length;
        int i = 0, j = 0;
        while (i < x && matrix[i][j] <= target) {
            i++;
        }
        if (i > 0) i--;
        while (j < y) {
            if (j < y && matrix[i][j] == target)
                return true;
            j++;
        }
        return false;
    }
}
赞(0) 打赏
未经允许不得转载:XINDOO » Leetcode 74. Search a 2D Matrix

评论 抢沙发

觉得文章有用就打赏一下文章作者

非常感谢你的打赏,我们将继续给力更多优质内容,让我们一起创建更加美好的网络世界!

支付宝扫一扫

微信扫一扫