本次练习将解决一个经典问题——在一个二维矩阵中查找特定的值。通过这个练习，可以更好地掌握二维数组的操作，以及优化算法的设计。
题目要求
给定一个二维矩阵 matrix，每行从左到右递增排序，每列从上到下递增排序，以及一个目标值 target。编写一个函数来判断目标值是否存在于矩阵中。如果存在，返回 true；否则，返回 false。
示例
输入：
matrix = [[1, 4, 7, 11],[2, 5, 8, 12],[3, 6, 9, 16],[10, 13, 14, 17]
]
若target = 5，输出：true若target = 20，输出：false解题思路
观察特性
- 每行从左到右递增，每列从上到下递增。
- 如果选择右上角或左下角的元素作为起点，可以通过比较值和 target，决定移动方向。
算法设计
- 从矩阵的右上角开始：
- 如果当前值等于 target，返回 true。
- 如果当前值大于 target，向左移动（减少列号）。
- 如果当前值小于 target，向下移动（增加行号）。
- 如果越界，则说明 target 不在矩阵中，返回 false。
时间复杂度分析
- 最多需要遍历一行和一列，总体复杂度为 O(m + n)，其中 m 和 n 分别为矩阵的行数和列数。
示例代码
C 实现
#include <stdio.h>
#include <stdbool.h>// 查找目标值是否存在于矩阵中
bool searchMatrix(int matrix[][4], int rows, int cols, int target) {int row = 0; // 从第一行int col = cols - 1; // 最后一列开始while (row < rows && col >= 0) {if (matrix[row][col] == target) {return true; // 找到目标值} else if (matrix[row][col] > target) {col--; // 当前值大于目标值，向左移动} else {row++; // 当前值小于目标值，向下移动}}return false; // 遍历结束未找到目标值
}int main()
{int matrix[4][4] = {{1, 4, 7, 11},{2, 5, 8, 12},{3, 6, 9, 16},{10, 13, 14, 17}};int target = 5;if (searchMatrix(matrix, 4, 4, target)) {printf("Target %d found in the matrix.\n", target);} else {printf("Target %d not found in the matrix.\n", target);}return 0;
}
C++ 实现
#include <iostream>
#include <vector>using namespace std;// 查找目标值是否存在于矩阵中
bool searchMatrix(vector<vector<int>>& matrix, int target) {int rows = matrix.size(); // 矩阵的行数int cols = matrix[0].size(); // 矩阵的列数int row = 0; // 从第一行int col = cols - 1; // 最后一列开始while (row < rows && col >= 0) {if (matrix[row][col] == target) {return true; // 找到目标值} else if (matrix[row][col] > target) {col--; // 当前值大于目标值，向左移动} else {row++; // 当前值小于目标值，向下移动}}return false; // 遍历结束未找到目标值
}int main()
{vector<vector<int>> matrix = {{1, 4, 7, 11},{2, 5, 8, 12},{3, 6, 9, 16},{10, 13, 14, 17}};int target = 5;if (searchMatrix(matrix, target)) {cout << "Target " << target << " found in the matrix." << endl;} else {cout << "Target " << target << " not found in the matrix." << endl;}return 0;
}
