leetcode 240. Search a 2D Matrix II

冷不防 2022-08-20 14:07 121阅读 0赞

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 in ascending from left to right.  
Integers in each column are sorted in ascending from top to bottom.  
For example,  
  
  
Consider the following matrix:  
  
  
\[  
  \[1,   4,  7, 11, 15\],  
  \[2,   5,  8, 12, 19\],  
  \[3,   6,  9, 16, 22\],  
  \[10, 13, 14, 17, 24\],  
  \[18, 21, 23, 26, 30\]  
\]  
Given target = 5, return true.

Given target = 20, return false.

class Solution {
    public:
    	bool searchMatrix(vector<vector<int>>& matrix, int target) {
    		if(matrix.empty())
    			return false;
    		if(matrix[0].empty())
    			return false;
    		if(matrix[0][0]>target||matrix[matrix.size()-1][matrix[0].size()-1]<target)
    			return false;
    		int curX=0,curY=0;
    		bool horizontal=true;
    		while(curX!=matrix[0].size()&&curY!=matrix.size())
    		{
    			if(horizontal)
    			{
    				while(curX!=matrix[0].size()&&matrix[curY][curX]<target)
    					curX++;
    				if(curX==matrix[0].size()||matrix[curY][curX]>target)
    				{
    					curX--;
    					horizontal=false;
    					curY++;
    				}
    				else
    					return true;
    			}
    			else
    			{
    				while(curY!=matrix.size()&&matrix[curY][curX]<target)
    					curY++;
    				if(curY==matrix.size()||matrix[curY][curX]>target)
    				{
    					if(curY==matrix.size()&&matrix[curY-1][curX]<target)
    						return false;
    					curY--;
    					horizontal=false;
    					curX--;
    				}
    				else
    					return true;
    			}
    		}
    		return false;
    	}
    };

accepted