240. 搜索二维矩阵 II
题目描述
输入一个 m x n 的整数矩阵 matrix 和一个整数 target。
矩阵有两个性质：每一行从左往右递增，每一列从上往下递增。
判断 target 是否出现在矩阵中，出现返回 true，否则返回 false。要求算法尽量高效。
示例 1
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]] target = 5 输出：true
解释：5 位于第 2 行第 2 列。
示例 2
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]] target = 20 输出：false
解释：矩阵中没有 20。
数据范围
m == matrix.lengthn == matrix[i].length1 <= n, m <= 300-10^9 <= matrix[i][j] <= 10^9- 每一行从左往右升序。
- 每一列从上往下升序。
-10^9 <= target <= 10^9
解题思路：右上角 Z 字形查找
从右上角开始：当前值大于 target 则左移，当前值小于 target 则下移。每步排除一整行或一整列。
为什么正确
指针所在位置的左下矩形仍包含所有可能的 target。
复杂度分析
时间 O(m+n)，空间 O(1)。
易错点
从左上角出发无法同时根据大小排除一整行或一整列。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def searchMatrix(self, matrix,target):
if not matrix: return False
r,c=0,len(matrix[0])-1
while r<len(matrix) and c>=0:
if matrix[r][c]==target: return True
if matrix[r][c]>target: c-=1
else: r+=1
return Falseclass Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length == 0) return false;
int r = 0, c = matrix[0].length - 1;
while (r < matrix.length && c >= 0) {
if (matrix[r][c] == target) return true;
if (matrix[r][c] > target) c--;
else r++;
}
return false;
}
}class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty()) return false;
int r = 0, c = matrix[0].size() - 1;
while (r < (int)matrix.size() && c >= 0) {
if (matrix[r][c] == target) return true;
if (matrix[r][c] > target) c--;
else r++;
}
return false;
}
};func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 {
return false
}
r, c := 0, len(matrix[0])-1
for r < len(matrix) && c >= 0 {
if matrix[r][c] == target {
return true
}
if matrix[r][c] > target {
c--
} else {
r++
}
}
return false
}var searchMatrix = function(matrix, target) {
if (!matrix.length) return false;
let r = 0, c = matrix[0].length - 1;
while (r < matrix.length && c >= 0) {
if (matrix[r][c] === target) return true;
if (matrix[r][c] > target) c--;
else r++;
}
return false;
};function searchMatrix(matrix: number[][], target: number): boolean {
if (!matrix.length) return false;
let r = 0, c = matrix[0].length - 1;
while (r < matrix.length && c >= 0) {
if (matrix[r][c] === target) return true;
if (matrix[r][c] > target) c--;
else r++;
}
return false;
};其他解法
逐行二分只用到行有序，O(m log n)；Z 字形查找同时利用行和列的有序性，每步排除一行或一列，O(m + n)。
解法 2：逐行二分 时间 O(m log n)，空间 O(1)
每一行都是升序的，对每一行单独做二分查找，任何一行找到 target 就返回 true。可以用行首剪枝：行首已大于 target 时，下面的行都不可能含 target。
只用到了“行有序”，写法简单。没有利用列有序来排除整行整列，当 m 和 n 接近时比 Z 字形查找慢。
import bisect
class Solution:
def searchMatrix(self, matrix, target):
for row in matrix:
if not row or row[0] > target:
break
i = bisect.bisect_left(row, target)
if i < len(row) and row[i] == target:
return True
return Falseclass Solution {
public boolean searchMatrix(int[][] matrix, int target) {
for (int[] row : matrix) {
if (row.length == 0 || row[0] > target) break;
int lo = 0, hi = row.length - 1;
while (lo <= hi) {
int mid = (lo + hi) >>> 1;
if (row[mid] == target) return true;
if (row[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
}
return false;
}
}class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
for (auto& row : matrix) {
if (row.empty() || row[0] > target) break;
auto it = lower_bound(row.begin(), row.end(), target);
if (it != row.end() && *it == target) return true;
}
return false;
}
};func searchMatrix(matrix [][]int, target int) bool {
for _, row := range matrix {
if len(row) == 0 || row[0] > target {
break
}
i := sort.SearchInts(row, target)
if i < len(row) && row[i] == target {
return true
}
}
return false
}var searchMatrix = function(matrix, target) {
for (const row of matrix) {
if (!row.length || row[0] > target) break;
let lo = 0, hi = row.length - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (row[mid] === target) return true;
if (row[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
}
return false;
};function searchMatrix(matrix: number[][], target: number): boolean {
for (const row of matrix) {
if (!row.length || row[0] > target) break;
let lo = 0, hi = row.length - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (row[mid] === target) return true;
if (row[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
}
return false;
}