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;
}