当前位置： 移动技术网 > IT编程>开发语言>C/C++ > LeetCode 74 Search a 2D Matrix（搜索2D矩阵）

LeetCode 74 Search a 2D Matrix（搜索2D矩阵）

2018年02月21日  | 移动技术网IT编程  | 我要评论

淘宝网耐克女鞋,测字网,亡灵至尊

翻译

写一个高效算法用于在一个m x n的矩阵中查找一个值。
这个矩阵有如下属性：

每行的整型数都是从左到右排序的。
每行的第一个元素都比上一行的最后一列大。

例如，
考虑如下矩阵：
[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
给定target = 3，返回true。

原文

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.
For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
Given target = 3, return true.

分析

可能因为我好困了，所以不论是算法还是我自己，都效率很低……

下面这个代码也是一改再改……

bool searchMatrix(vector>& matrix, int target) {
    if (matrix[0][0] > target) return false;
    for (int i = 0; i < matrix.size(); ) {
        for (int j = 0; j < matrix[i].size(); ) {
            if (i == matrix.size() - 1 && matrix[i][j] < target) {
                if (j >= matrix[i].size()) return false;
                j += 1;
                if (matrix[i][j] > target) return false;
            }
            else if (matrix[i][j] < target && matrix[i+1][j] > target) {
                j += 1;
                if (j >= matrix[i].size()) return false;
                if (matrix[i][j] > target) return false;
            }
            else if (matrix[i][j] < target && matrix[i + 1][j] <= target) {
                i += 1;
            }
            else if (matrix[i][j] == target) {
                return true;
            }     
            if (i == matrix.size() - 1 && j == matrix[i].size() ) {
                return false;
            }
        }
    }
    return false;
}

明天再整理整理思路重新做一遍吧……

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网