6

Leetcode 74. Search a 2D Matrix | XINDOO

 3 years ago
source link: https://zxs.io/article/920
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Leetcode 74. Search a 2D Matrix
当前位置：XINDOO > 算法 > 正文

题目链接：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;
    }
}
赏

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK