C++ 中的矩阵介绍：以二维矩阵查找为例
在 C++ 编程中，矩阵是一种非常常见的数据结构。它本质上可以理解为一个二维表格，由若干行和若干列组成。矩阵常用于图像处理、动态规划、搜索算法、图论、数学计算等场景。
例如下面这个矩阵：
vector<vector<int>> 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} };可以看成一个 5 行 5 列的二维表：
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在 C++ 中，我们通常使用：
vector<vector<int>>来表示一个二维矩阵。
一、什么是矩阵？
矩阵可以理解为一个由行和列组成的数据集合。
例如：
a[0][0] a[0][1] a[0][2] a[1][0] a[1][1] a[1][2] a[2][0] a[2][1] a[2][2]其中：
matrix[i][j]表示矩阵中第i行第j列的元素。
需要注意的是，C++ 中数组下标是从0开始的。
也就是说：
matrix[0][0]表示第一行第一列的元素。
matrix[1][2]表示第二行第三列的元素。
二、C++ 中矩阵的常见表示方式
1. 使用二维数组表示矩阵
如果矩阵大小固定，可以使用二维数组：
int matrix[3][3] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };访问元素：
cout << matrix[0][1]; // 输出 2二维数组的优点是访问速度快，结构简单。
缺点是大小通常需要提前确定，灵活性较差。
2. 使用 vector 表示矩阵
在算法题和实际开发中，更常用的是：
vector<vector<int>> matrix;例如：
vector<vector<int>> matrix = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };它的结构可以理解为：
vector< vector<int> >也就是说，外层vector存储每一行，内层vector<int>存储这一行中的每个元素。
例如：
matrix[0] = {1, 2, 3}; matrix[1] = {4, 5, 6}; matrix[2] = {7, 8, 9};因此：
matrix[1][2]就是第 2 行第 3 列的元素，也就是6。
三、如何获取矩阵的行数和列数？
在你的代码中：
int rows = matrix.size(); int cols = matrix[0].size();这两行非常重要。
其中：
matrix.size()表示矩阵有多少行。
matrix[0].size()表示矩阵第一行有多少列。
例如：
vector<vector<int>> matrix = { {1, 2, 3}, {4, 5, 6} };这个矩阵有 2 行 3 列。
所以：
matrix.size(); // 2 matrix[0].size(); // 3四、为什么要判断空矩阵？
你的代码中有这样一段：
if (matrix.empty() || matrix[0].empty()) { return false; }这是一个非常好的习惯。
因为如果矩阵为空：
vector<vector<int>> matrix;此时直接访问：
matrix[0]会发生越界错误。
所以在访问矩阵元素之前，应该先判断矩阵是否为空。
完整判断方式如下：
if (matrix.empty() || matrix[0].empty()) { return false; }含义是：
matrix.empty()判断矩阵是否没有任何行。
matrix[0].empty()判断第一行是否没有任何元素。
五、如何遍历一个矩阵？
最常见的方式是使用双重循环。
for (int i = 0; i < matrix.size(); i++) { for (int j = 0; j < matrix[0].size(); j++) { cout << matrix[i][j] << " "; } cout << endl; }外层循环控制行：
for (int i = 0; i < rows; i++)内层循环控制列：
for (int j = 0; j < cols; j++)访问元素：
matrix[i][j]例如矩阵：
1 2 3 4 5 6 7 8 9遍历顺序就是：
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9六、通过代码理解矩阵查找
你的代码实现的是一个非常经典的问题：
在一个行和列都按升序排列的矩阵中查找目标值。
矩阵如下：
vector<vector<int>> matrix1 = { {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} };这个矩阵有两个特点：
每一行从左到右递增。
1 < 4 < 7 < 11 < 15每一列从上到下递增。
1 < 2 < 3 < 10 < 18所以我们可以利用这个性质来提高查找效率。
七、为什么从右上角开始查找？
你的代码中是从右上角开始查找的：
int row = 0; int col = cols - 1;也就是从：
matrix[0][cols - 1]开始。
以示例矩阵为例，右上角元素是：
151 4 7 11 [15] 2 5 8 12 19 3 6 9 16 22 10 13 14 17 24 18 21 23 26 30为什么选择右上角？
因为右上角这个位置非常特殊：
它所在的这一行中，它是当前行最大的元素。
它所在的这一列中，它是当前列最小的元素。
所以：
如果当前值比目标值大，说明当前列下面的元素更大，更不可能是答案，只能向左移动。
如果当前值比目标值小，说明当前行左边的元素更小，更不可能是答案，只能向下移动。
这样每次都可以排除一整行或者一整列。
八、核心查找逻辑分析
核心代码如下：
while (row < rows && col >= 0) { if (matrix[row][col] == target) { return true; } else if (matrix[row][col] > target) { col--; } else { row++; } }这段代码的逻辑是：
当前位置元素等于目标值，说明找到了，直接返回true。
if (matrix[row][col] == target) { return true; }当前位置元素大于目标值，说明当前元素太大，需要往更小的方向走，也就是向左移动。
else if (matrix[row][col] > target) { col--; }当前位置元素小于目标值，说明当前元素太小，需要往更大的方向走，也就是向下移动。
else { row++; }当row超出矩阵行数，或者col小于 0 时，说明已经查找完整个可能区域，仍然没有找到目标值。
return false;九、以 target = 5 为例分析查找过程
矩阵如下：
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;从右上角开始：
matrix[0][4] = 1515 > 5，向左移动。
matrix[0][3] = 1111 > 5，继续向左移动。
matrix[0][2] = 77 > 5，继续向左移动。
matrix[0][1] = 44 < 5，向下移动。
matrix[1][1] = 5找到了目标值，返回true。
十、以 target = 20 为例分析查找过程
目标值：
target = 20;查找过程如下：
15 < 20，向下移动 19 < 20，向下移动 22 > 20，向左移动 16 < 20，向下移动 17 < 20，向下移动 24 > 20，向左移动 14 < 20，向下移动 23 > 20，向左移动 21 > 20，向左移动 18 < 20，向下移动最终row超出矩阵范围，说明矩阵中没有20，返回false。
十一、完整代码
#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 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() { Solution sol; vector<vector<int>> matrix1 = { {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} }; int target1 = 5; cout << "Input: target = 5" << endl; cout << "Output: " << (sol.searchMatrix(matrix1, target1) ? "true" : "false") << endl; int target2 = 20; cout << "Input: target = 20" << endl; cout << "Output: " << (sol.searchMatrix(matrix1, target2) ? "true" : "false") << endl; return 0; }十二、时间复杂度分析
这个算法不是普通的双重循环遍历。
如果使用普通遍历，需要检查每一个元素：
for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (matrix[i][j] == target) { return true; } } }这种方式的时间复杂度是：
O(m * n)其中m是行数，n是列数。
而你的代码每次只会向左或者向下移动一步。
最多移动：
m + n次。
所以时间复杂度是：
O(m + n)空间复杂度是：
O(1)因为没有使用额外的数据结构。
十三、矩阵在 C++ 中的常见应用
矩阵在 C++ 算法中非常常见，尤其是在以下场景：
1. 搜索问题
例如：
二维矩阵查找 岛屿数量 单词搜索 迷宫问题这些问题通常需要在矩阵中进行上下左右移动。
2. 动态规划
很多动态规划问题也会使用二维矩阵，例如：
最长公共子序列 编辑距离 最小路径和 不同路径通常会定义：
vector<vector<int>> dp;用来保存状态。
3. 图像处理
图像本质上也可以看成矩阵。
例如一张灰度图可以看成：
0 23 45 88 120 255 34 76 200每个数字代表一个像素点的灰度值。
4. 棋盘类问题
例如：
N 皇后 数独 扫雷 五子棋 围棋这些问题都可以使用二维矩阵来表示棋盘状态。
十四、C++ 矩阵编程的注意事项
1. 访问前一定要判断是否为空
错误写法：
int cols = matrix[0].size();如果矩阵为空，这行代码会报错。
推荐写法：
if (matrix.empty() || matrix[0].empty()) { return false; }2. 注意行和列不要写反
一般来说：
matrix[i][j]其中：
i 表示行 j 表示列行数：
matrix.size()列数：
matrix[0].size()3. 注意下标越界
矩阵下标从0开始。
如果一个矩阵有rows行，那么合法的行下标范围是：
0 到 rows - 1如果一个矩阵有cols列，那么合法的列下标范围是：
0 到 cols - 1所以循环条件通常写成：
for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { cout << matrix[i][j] << endl; } }而不是：
i <= rows j <= cols十五、总结
矩阵是 C++ 中非常重要的数据结构，本质上就是一个二维容器。
在 C++ 中，常见的矩阵表示方式有两种：
int matrix[100][100];和：
vector<vector<int>> matrix;在算法题中，更推荐使用vector<vector<int>>，因为它更加灵活，适合动态创建矩阵。
通过本题可以看到，如果矩阵本身具有某种有序性质，我们就可以利用这种性质优化查找过程。
从右上角开始查找的核心思想是：
当前值太大，就向左走； 当前值太小，就向下走； 等于目标值，就返回 true。这种方法充分利用了矩阵“每一行递增、每一列递增”的特点，将原本O(m * n)的暴力查找优化到了O(m + n)。