LeetCode in Python 74/240. Search a 2D Matrix I/II (搜索二维矩阵I/II)

本文主要是介绍LeetCode in Python 74/240. Search a 2D Matrix I/II (搜索二维矩阵I/II)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

搜索二维矩阵I其实可以转换为搜索一维数组，原因在于，只要先确定搜索的整数应该在哪一行，即可对该行进行二分查找。

搜索二维矩阵II中矩阵元素排列方式与I不同，但思想大致相同。

目录

LeetCode in Python 74.

LeetCode in Python 240. 

LeetCode in Python 74.

示例：

图1 搜索二维矩阵输入输出示例

代码：

class Solution:def searchMatrix(self, matrix, target):m, n = len(matrix), len(matrix[0])def binaSearch(i, j, target):l, r = 0, jwhile l <= r:mid = (l + r) // 2if target > matrix[i][mid]:l = mid + 1elif target < matrix[i][mid]:r = mid - 1else:return Truereturn Falsefor i in range(m):if target < matrix[i][n - 1]:return binaSearch(i, n - 1, target)elif target > matrix[i][n - 1]:i += 1else:return Truereturn False

 解释：

1）首先要判断target可能在哪一行，判断标准是将target与矩阵每一行最后一个元素比较，若大于该元素，则表明target在下一行，反之在这一行(按序一行一行比较)。在确定在哪一行之后，利用二分法在该行查找是否有target，有则True，无则False：

        for i in range(m):

                if target < matrix[i][n - 1]:

                        return binaSearch(i, n - 1, target)

               elif target > matrix[i][n - 1]:

                        i += 1

              else:

                       return True

       return False

2）在二分查找中注意，target对比的元素为matrix[i][mid]，i代表target可能存在的行，即传过去的参数i。

LeetCode in Python 240. 

示例：

 

图2 搜索矩阵II输入输出示意图 

代码：

class Solution:def searchMatrix(self, matrix, target):m, n = len(matrix), len(matrix[0])r, c = m - 1, 0while r >= 0 and c < n:if target > matrix[r][c]:c += 1elif target < matrix[r][c]:r -= 1else:return Truereturn False 

解释：

1）先确定列再确定行，即从矩阵左下角元素开始比较，target>该元素则右移，反之上移直到找到target返回True或无target返回False。

这篇关于LeetCode in Python 74/240. Search a 2D Matrix I/II (搜索二维矩阵I/II)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---