首页 > 代码库 > 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.

 

For example,

Consider the following matrix:

[  [1,   3,  5,  7],  [10, 11, 16, 20],  [23, 30, 34, 50]]

Given target = 3, return true.

C++实现代码如下:

#include<iostream>#include<vector>using namespace std;class Solution{public:    bool searchMatrix(vector<vector<int> > &matrix, int target)    {        if(matrix.empty()||matrix[0].empty())            return false;        int i=0;        int j=matrix[0].size()-1;        int temp;        while(i<(int)matrix.size()&&j>=0)        {            temp=matrix[i][j];            if(target==temp)                return true;            else if(target<temp)                j--;            else if(target>temp)                i++;        }        return false;    }};int main(){    Solution s;    vector<vector<int> > vec=    {        {-10,-9},        {-7,-6},        {-5,-4},        {-3,-2}    };    cout<<s.searchMatrix(vec,-6)<<endl;}

开始提交了一种,死活通不过。

class Solution {public:    bool searchMatrix(vector<vector<int> > &matrix, int target) {        if(matrix.empty()||matrix[0].empty())            return false;        size_t i=0;        size_t j=matrix[0].size()-1;        int temp;        while(i<matrix.size()&&j>=0)        {            temp=matrix[i][j];            if(target==temp)                return true;            if(target<temp)            {                j--;                continue;            }            if(target>temp)            {                i++;                continue;            }        }        if(i>=matrix.size()||j<0)            return false;        return true;    }};

一直报错Last executed input:[[-10],[-7],[-4]], -6

就因为将i和j声明为size_t类型,可能出现下溢。可以参考:https://oj.leetcode.com/discuss/11366/why-is-the-last-executed-input-error

Search a 2D Matrix