Leetcode12: Search a 2D Matrix

Leetcode12: 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.

  這是一個楊氏矩陣，即每一行是遞增的，每一列也是遞增的。根據遞增性質，我們對每一行只搜索最後一個數，如果小於target那麼前往下一行，如果大於target那麼說明在這一行，於是前往前一列，直到找到該數。

   

  class Solution {
  public:
      bool searchMatrix(vector > &matrix, int target) {
          int m = matrix.size();
          int n = matrix[0].size();
          for(int row = 0, col = n-1; row < m && col >= 0;)
          {
              if(matrix[row][col] < target)
              {
                  row++;
              }
              else if(matrix[row][col] > target)
              {
                  col--;
              }
              else
                  return true;
          }
          return false;
      }
  };

  

   

   

  這道題難度是medium，本來我打算先把easy難度的做完在考慮中等難度的。偶然看了七月算法的視頻（排序查找實戰），受益匪淺，決定對講過的例題進行鞏固消化，於是先把這道題做了，算法思路來源於曹博，學習了！