C++ 中的矩阵介绍：以二维矩阵查找为例

在 C 编程中矩阵是一种非常常见的数据结构。它本质上可以理解为一个二维表格由若干行和若干列组成。矩阵常用于图像处理、动态规划、搜索算法、图论、数学计算等场景。例如下面这个矩阵vectorvectorint 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 中我们通常使用vectorvectorint来表示一个二维矩阵。一、什么是矩阵矩阵可以理解为一个由行和列组成的数据集合。例如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 表示矩阵在算法题和实际开发中更常用的是vectorvectorint matrix;例如vectorvectorint matrix { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };它的结构可以理解为vector vectorint 也就是说外层vector存储每一行内层vectorint存储这一行中的每个元素。例如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()表示矩阵第一行有多少列。例如vectorvectorint matrix { {1, 2, 3}, {4, 5, 6} };这个矩阵有 2 行 3 列。所以matrix.size(); // 2 matrix[0].size(); // 3四、为什么要判断空矩阵你的代码中有这样一段if (matrix.empty() || matrix[0].empty()) { return false; }这是一个非常好的习惯。因为如果矩阵为空vectorvectorint 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六、通过代码理解矩阵查找你的代码实现的是一个非常经典的问题在一个行和列都按升序排列的矩阵中查找目标值。矩阵如下vectorvectorint 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(vectorvectorint 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; vectorvectorint 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. 动态规划很多动态规划问题也会使用二维矩阵例如最长公共子序列 编辑距离 最小路径和 不同路径通常会定义vectorvectorint 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];和vectorvectorint matrix;在算法题中更推荐使用vectorvectorint因为它更加灵活适合动态创建矩阵。通过本题可以看到如果矩阵本身具有某种有序性质我们就可以利用这种性质优化查找过程。从右上角开始查找的核心思想是当前值太大就向左走 当前值太小就向下走 等于目标值就返回 true。这种方法充分利用了矩阵“每一行递增、每一列递增”的特点将原本O(m * n)的暴力查找优化到了O(m n)。