LeetCode240:Search a 2D Matrix II

LeetCode240:Search a 2D Matrix II

Write an efficient algorithm that searches for a value in anmxnmatrix. 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]
  ]
  

  Giventarget=5, returntrue.

  Giventarget=20, returnfalse.

  Subscribeto see which companies asked this question

  //時間復雜度為O(m+n)
  class Solution{
  public:
  	bool searchMatrix(vector>& matrix, int target) {
  		int m = matrix.size();
  		int n = matrix[0].size();
  
  		int i = 0, j = n - 1;
  		while (i < m && j >= 0)
  		{
  			if (matrix[i][j] == target)
  				return true;
  			else if (matrix[i][j] > target)
  				j--;
  			else
  				i++;
  		}
  		return false;
  	}
  };