程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Leetcode12: Search a 2D Matrix

Leetcode12: Search a 2D Matrix

編輯:關於C++

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難度的做完在考慮中等難度的。偶然看了七月算法的視頻(排序查找實戰),受益匪淺,決定對講過的例題進行鞏固消化,於是先把這道題做了,算法思路來源於曹博,學習了!
     

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved