Search 2D matrix 2

 

Search for a two-dimensional matrix

This problem is equivalent to a brain teaser , Just know how to do it ,ok

Ideas ：

We can set the starting point to the upper right corner at the beginning ,

Here we can divide into three situations

1.t==target

2.t>target, If t>target, Then we can get rid of this column , because t The numbers below this column are greater than t

3.t<target, If t<target Then this line can be removed . Because in this business t Maximum .

  step ：

1. First create two variables to represent the coordinates of the upper right corner

2. Then take the condition that the coordinates of the point cannot cross the boundary as the cycle , Start the cycle

3. With t Represents the coordinate value , First three situations .

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