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
     
      #include
      
       using namespace std;class Solution{public:    bool searchMatrix(vector
       
        
          > &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)                i++;        }        return false;    }};int main(){    Solution s;    vector
          
           
             > vec= { { -10,-9}, { -7,-6}, { -5,-4}, { -3,-2} }; cout<
            
             <
            
           
          
         
        
       
      
     

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

class Solution {public:    bool searchMatrix(vector
     
      
        > &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
       
        =0)        {            temp=matrix[i][j];            if(target==temp)                return true;            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类型，可能出现下溢。可以参考：