1、题目描述

https://leetcode-cn.com/problems/search-a-2d-matrix/

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。

该矩阵具有如下特性：

每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数（变成了240题的特例）。

通用模板就看 LeetCode240：搜索二维矩阵II https://blog.csdn.net/IOT_victor/article/details/104642324

本题解法在240基础上加了优化

2、代码详解

法一：缩小领域法

因为每一行递增，每一列递增。所以我们可以从右上角往左下角找或者从左下角往右上角找。

每次比较可以排除一行或者一列，时间复杂度为O(m+n)

class Solution(object): def searchMatrix(self, matrix, target): # m * n m = len(matrix) if m == 0: return False n = len(matrix[0]) # 左下角（必须这么设置！左下角：最后一行的最小值）从下向上 row = m - 1 col = 0 while row >= 0 and col <= n-1: # 优化:当前行的最大值 < target if matrix[row][n-1] < target: return False if matrix[row][col] > target: row -= 1 elif matrix[row][col] < target: col += 1 else: return True return False # # 右上角（必须这么设置！右上角：第一行的最大值）从上向下 # row = 0 # 行 # col = n - 1 # 列 # while row <= m-1 and col >= 0: # # 优化:当前行的最小值 > target # if matrix[row][0] > target: # return False # if matrix[row][col] > target: # 在本行中 # col -= 1 # elif matrix[row][col] < target: # 加行 # row += 1 # else: # return True # return False matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3 s = Solution() print(s.searchMatrix(matrix, target))

法二：标准的二分查找模板

将二维矩阵拖为一维矩阵，然后就是一个有序的一维数组了，利用二分查找就行