Leetcode 240. Search a 2D Matrix II

Problem

Write an efficient algorithm that searches for a value target in an m x n integer matrix 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.
  

Algorithm

Choose the top-right corner (or bottom-left corner) as the starting position, and then repeat the following process:

• If the current element is equal to the target, then end.
  
• If the current element is greater than the target, all elements to the bottom-right are larger, so move left.
  
• If the current element is smaller than the target, all elements to the top-left are smaller, so move down.
  

The time complexity is                                    O                         (                         m                         +                         n                         )                              O(m+n)                  O(m+n).
Code

1. class Solution:
2.     def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
3.         if not matrix or not matrix[0]:
4.             return False
5.         
6.         rows, cols = len(matrix), len(matrix[0])
7.         r, c = 0, cols-1
8.         while r < rows and c >= 0:
9.             if matrix[r][c] == target:
10.                 return True
11.             elif matrix[r][c] > target:
12.                 c -= 1
13.             else:
14.                 r += 1
15.         
16.         return False

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。