二维数组“降维”到一维数组----从零开始的算法

一.核心前提核心前提元素总数不变且操作基于“行优先遍历”顺序这里的行优先对象指的是二维数组。• 适用场景当题目要求将一个矩阵按特定顺序重新排列为新的行、列维度且元素顺序在内存中的线性排列保持一致时就可以使用一维下标作为中间桥梁。适用场景包括矩阵变形如 LeetCode 566将m×n矩阵转为r×c矩阵。图像处理将 RGB 图像的 3 维数组展平为一维向量输入神经网络Flatten 层。数据扁平化将二维表格数据按行拼接成一维数组用于存储或传输。矩阵运算底层优化在实现矩阵乘法、卷积等操作时将矩阵按行主序或列主序线性化利用 CPU 缓存局部性加速计算。条件你只需要按线性下标顺序逐个搬运元素而不涉及复杂的旋转、转置或条件筛选。因为线性下标与二维坐标的映射是双射一一对应所以只要总数相同任意合法维度都可重塑。二.行主序 or 列主序顾名思义行主序Row-major order在内存中同一行的元素连续存放行与行之间顺序排列。即第一行的所有元素 → 第二行的所有元素 → … → 最后一行的所有元素。列主序Column-major order在内存中同一列的元素连续存放列与列之间顺序排列。即第一列的所有元素 → 第二列的所有元素 → … → 最后一列的所有元素。例子;示例矩阵[[1,2,3],[4,5,6]]存储顺序内存中的线性排列下标从0开始行主序[1, 2, 3, 4, 5, 6]列主序[1, 4, 2, 5, 3, 6]• 坐标映射:坐标映射公式设矩阵列数为C总列数固定存储顺序二维坐标(row, col)→ 一维下标index一维下标index→ 二维坐标(row, col)行主序index row * C colrow index / Ccol index % C列主序index col * R rowR为行数row index % Rcol index / R补充性能影响局部性原理行主序访问行元素连续内存缓存命中率高速度极快。行主序访问列元素内存跳跃缓存频繁失效速度慢可能慢几十倍例题leetcode 566 重塑数组在 MATLAB 中有一个非常有用的函数reshape它可以将一个m x n矩阵重塑为另一个大小不同r x c的新矩阵但保留其原始数据。给你一个由二维数组mat表示的m x n矩阵以及两个正整数r和c分别表示想要的重构的矩阵的行数和列数。重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。如果具有给定参数的reshape操作是可行且合理的则输出新的重塑矩阵否则输出原始矩阵。示例 1输入mat [[1,2],[3,4]], r 1, c 4输出[[1,2,3,4]]示例 2输入mat [[1,2],[3,4]], r 2, c 4输出[[1,2],[3,4]]#includeiostream #includevector using namespace std; class Solution { public: vectorvectorint matrixReshape(vectorvectorint mat, int r, int c) { int m mat.size(); int n mat[0].size(); if (m*n ! r*c) return mat; vectorvectorint answer(r,vectorint(c,0)); for (int i 0; i m; i){ for (int j 0; j n; j){ int newrow 0,newcol 0; int temp i*n j; newrow temp / c; newcol temp % c; answer[newrow][newcol] mat[i][j]; } } return answer; } };或者也可以#includeiostream #includevector using namespace std; class Solution { public: vectorvectorint matrixReshape(vectorvectorint mat, int r, int c) { int m mat.size(); int n mat[0].size(); if (m * n ! r *c) { return mat; } vectorvectorint answer(r,vectorint(c)); for (int i 0; i m*n ; i){ int newRow i / c; //第i行 int newcol i % c; // 第j个 新的 int oldRow i / n; int oldcol i % n; answer[newRow][newcol] mat[oldRow][oldcol]; } return answer; } };两者的时间复杂度和空间复杂度都是一样的前者更加接近于模拟的方式便于理解。本章是学习哈希表做题的时候发现的问题特此单开一章用于总结。希望正在阅读的你有所帮助。喜欢我的话可以点点免费的赞和关注谢谢支持