频道栏目
首页 > 考试 > 其他 > 正文

LeetCode OJ-74.Search a 2D Matrix

2017-01-16 10:06:08         来源:oYinGui1  
收藏   我要投稿

LeetCode OJ-74.Search a 2D Matrix

题目描述

Write an efficient algorithm that searches for a value in anmxnmatrix. 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]
]

Giventarget=3, returntrue.

Subscribeto see which companies asked this question

题目理解

在一个二维矩阵中,求解target是否存在。可以将二维转化为一维,在一维数组中去寻找。时间复杂度为O(m * n),空间复杂度为O(1)。具体代码如下:

Code

bool search_matrix(vector<vector<int>> &matrix, int target)
{
    int row = (int) matrix.size();
    int col = (row > 0) ? (int) matrix[0].size() : 0;  //判断是否是空vector
    int sz = row * col;
    int i;
    for (i = 0; i < sz; ++i) {
        if (matrix[i / col][i % col] == target) {  //将二维转化为一维
            return true;
        }
    }

    return false;
}
上一篇:【leetcode】20. Valid Parentheses
下一篇:leetcode - 1 two sum
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站