#P4024. 搜索二维矩阵
-
ID: 2240
Tried: 63
Accepted: 27
Difficulty: 4
搜索二维矩阵
题目内容
给你一个满足下述两条属性的 m×n整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，输出 true ；否则，输出 false。
输入描述
第一行包含两个整数 m 和 n，分别表示矩阵的行数和列数。
接下来的 m 行，每行包含 n 个整数，表示矩阵的元素。
最后一行包含一个整数 target。
输出描述
如果 target 存在于矩阵中，则输出 true，否则输出 false。输出不用考虑大小写。
样例1
输入
3 4
1 3 5 7
10 11 16 20
23 30 34 60
3
输出
true
样例2
输入
3 4
1 3 5 7
10 11 16 20
23 30 34 60
13
输出
false
提示
- m==matrix.length
- n==matrix[i].length
- 1<=m,n<=100
- −104<=matrix[i][j],target<=104
搜索二维矩阵
算法思路
题目给定的矩阵满足以下两个条件：
- 每行中整数从左到右非严格递增排列；
- 每行的第一个整数大于上一行最后一个整数。
这两个条件说明整个矩阵可以看作一个有序的一维数组。可以将矩阵的下标映射为一维下标，然后使用二分查找算法快速判断目标值是否存在。具体做法如下：
- 计算矩阵总元素个数，并用二分查找在区间 [0, m*n-1] 内进行搜索。
- 通过映射关系：二维下标(row, col) = (index // n, index % n)，将一维下标转换为对应的矩阵位置，比较该位置的数值与 target。
- 根据比较结果调整二分查找区间，直至找到目标或区间为空。
这种方法的时间复杂度为 O(log(m*n))，空间复杂度为 O(1)。
复杂度分析
- 时间复杂度：O(log(m*n))，二分查找每次将搜索区间折半。
- 空间复杂度：O(1)，只使用了常数级额外空间。
Python 代码
class Solution:
def searchMatrix(self, matrix, target):
if not matrix or not matrix[0]:
return False
m, n = len(matrix), len(matrix[0])
left, right = 0, m * n - 1
# 二分查找过程
while left <= right:
mid = (left + right) // 2
row = mid // n # 一维下标映射为二维行下标
col = mid % n # 一维下标映射为二维列下标
mid_value = matrix[row][col]
if mid_value == target:
return True
elif mid_value < target:
left = mid + 1
else:
right = mid - 1
return False
if __name__ == "__main__":
import sys
# 读取输入数据
data = sys.stdin.read().split()
if not data:
exit(0)
# 第一行包含 m 和 n
m = int(data[0])
n = int(data[1])
matrix = []
# 接下来 m 行，每行 n 个整数
index = 2
for _ in range(m):
row = []
for _ in range(n):
row.append(int(data[index]))
index += 1
matrix.append(row)
# 最后一行是 target
target = int(data[index])
solution = Solution()
result = solution.searchMatrix(matrix, target)
# 根据要求输出 "true" 或 "false"
print("true" if result else "false")
Java 代码
import java.util.Scanner;
public class Main {
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int m = matrix.length;
int n = matrix[0].length;
int left = 0, right = m * n - 1;
// 二分查找
while(left <= right) {
int mid = left + (right - left) / 2;
int row = mid / n; // 映射为二维数组行下标
int col = mid % n; // 映射为二维数组列下标
int midValue = matrix[row][col];
if(midValue == target) {
return true;
} else if(midValue < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
}
// main函数，用于读取输入和输出结果
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取矩阵的行数 m 和列数 n
int m = sc.nextInt();
int n = sc.nextInt();
int[][] matrix = new int[m][n];
// 读取矩阵数据
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = sc.nextInt();
}
}
// 读取目标值 target
int target = sc.nextInt();
sc.close();
Main main = new Main();
Solution solution = main.new Solution();
boolean result = solution.searchMatrix(matrix, target);
// 输出结果：true 或 false
System.out.println(result ? "true" : "false");
}
}
C++ 代码
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.empty() || matrix[0].empty()) return false;
int m = matrix.size();
int n = matrix[0].size();
int left = 0, right = m * n - 1;
// 二分查找
while(left <= right) {
int mid = left + (right - left) / 2;
int row = mid / n; // 映射为二维数组行下标
int col = mid % n; // 映射为二维数组列下标
int midValue = matrix[row][col];
if(midValue == target) {
return true;
} else if(midValue < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
};
int main() {
int m, n;
// 读取矩阵的行数 m 和列数 n
cin >> m >> n;
vector<vector<int>> matrix(m, vector<int>(n));
// 读取矩阵数据
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> matrix[i][j];
}
}
int target;
// 读取目标值 target
cin >> target;
Solution solution;
bool result = solution.searchMatrix(matrix, target);
// 输出结果：true 或 false
cout << (result ? "true" : "false") << endl;
return 0;
}