一份完整的网站策划方案,宁波网站推广联系方式,做的网站需要什么技术,猫扑网站开发的网络游戏废话不多说#xff0c;喊一句号子鼓励自己#xff1a;程序员永不失业#xff0c;程序员走向架构#xff01;本篇Blog的主题是螺旋矩阵#xff0c;使用【二维数组】这个基本的数据结构来实现
螺旋矩阵【EASY】
二维数组的结构特性入手
题干 解题思路
根据题目示例 mat…废话不多说喊一句号子鼓励自己程序员永不失业程序员走向架构本篇Blog的主题是螺旋矩阵使用【二维数组】这个基本的数据结构来实现
螺旋矩阵【EASY】
二维数组的结构特性入手
题干 解题思路
根据题目示例 matrix [[1,2,3],[4,5,6],[7,8,9]] 的对应输出 [1,2,3,6,9,8,7,4,5] 可以发现顺时针打印矩阵的顺序是 “从左向右、从上向下、从右向左、从下向上” 循环。
因此考虑设定矩阵的 “左、上、右、下” 四个边界模拟以上矩阵遍历顺序算法流程
空值处理 当 matrix 为空时直接返回空列表 [] 即可。初始化 矩阵 左、右、上、下 四个边界 l , r , t , b 用于打印的结果列表 res 。循环打印 “从左向右、从上向下、从右向左、从下向上” 四个方向循环打印。 根据边界打印即将元素按顺序添加至列表 res 尾部。边界向内收缩 1 代表已被打印。** 判断边界是否相遇**是否打印完毕若打印完毕代表下一个方向无需打印则跳出。 返回值 返回 res 即可。 整体的打印过程
代码实现 基本数据结构数组 辅助数据结构无 算法无 技巧无 import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param matrix int整型二维数组* return int整型ArrayList*/public ArrayListInteger spiralOrder (int[][] matrix) {// 1 入参判断如果为空数组返回空集合if (matrix.length 1) {return new ArrayListInteger();}// 2 定义四条边及返回值ArrayListInteger result new ArrayListInteger();int left 0;int right matrix[0].length - 1;int top 0;int bottom matrix.length - 1;// 3 循环打印四条边while (true) {// 3-1 从左向右打印,明确左右边界打印完后上边界向下移动,并判断是否有必要继续从上到下打印for (int i left; i right; i) {result.add(matrix[top][i]);}if (top bottom) {break;}// 3-2 从上向下打印,明确上下边界打印完后右边界向左移动,并判断是否有必要继续从右到左打印for (int i top; i bottom; i) {result.add(matrix[i][right]);}if (left --right) {break;}// 3-3 从右向左打印,明确左右边界打印完后下边界向上移动,并判断是否有必要继续从下到上打印for (int i right; i left; i--) {result.add(matrix[bottom][i]);}if (top --bottom) {break;}// 3-4 从下向上打印,明确上下边界打印完后左边界向右移动,并判断是否有必要继续从左到右打印for (int i bottom; i top; i--) {result.add(matrix[i][left]);}if (left right) {break;}}return result;}
}top bottom 等价于先给 top 自增 1 再判断top bottom 逻辑表达式
复杂度分析
时间复杂度 O(MN) M,N分别为矩阵行数和列数。空间复杂度 O(1) 四个边界 l , r , t , b 使用常数大小的额外空间。
旋转图像
和螺旋矩阵类似也是对一圈数值做处理
题干 解题思路
由原题知整体的旋转公式如下 如果可以使用辅助矩阵则按如下方式修改即可
class Solution {public void rotate(int[][] matrix) {int n matrix.length;// 深拷贝 matrix - tmpint[][] tmp new int[n][];for (int i 0; i n; i)tmp[i] matrix[i].clone();// 根据元素旋转公式遍历修改原矩阵 matrix 的各元素for (int i 0; i n; i) {for (int j 0; j n; j) {matrix[j][n - 1 - i] tmp[i][j];}}}
}考虑不借助辅助矩阵通过在原矩阵中直接「原地修改」实现空间复杂度 **O(1)**的解法。以位于矩阵四个角点的元素为例设矩阵左上角元素 A 、右上角元素 B 、右下角元素 C 、左下角元素 D 。矩阵旋转 90º 后相当于依次先后执行 D→AC→D, B→C, A→B 修改元素即如下「首尾相接」的元素旋转操作 如上图所示由于第 1 步 D→A已经将 A覆盖导致 A 丢失此丢失导致最后第 4步 A→B无法赋值。为解决此问题考虑借助一个「辅助变量 tmp」预先存储 A 此时的旋转操作变为 如上图所示一轮可以完成矩阵 4 个元素的旋转。因而只要分别以矩阵左上角 1/4的各元素为起始点执行以上旋转操作
将这些元素旋转完成即完成了整个数组的旋转 具体来看当矩阵大小n为偶数时行列均取前n/2当矩阵大小为奇数时行取n/2列取n1/2因为为奇数时中间的元素不需要旋转
代码实现 基本数据结构数组 辅助数据结构无 算法无 技巧无 class Solution {public void rotate(int[][] matrix) {// 1 获取数组长度依据替换顺序位置matrix[i][j]-matrix[j][n-1-i]推导出ABCD位置int n matrix.length;//int amatrix[i][j];int bmatrix[j][n-1-i];int cmatrix[n-1-i][n-1-j];int dmatrix[n-1-j][i];// 2 遍历行列行取n/2,列取n1/2 为了应对奇数长度的nfor (int i 0; i n / 2; i) {for (int j 0; j (n 1) / 2; j) {// 2-1 暂存A的位置用来后续替换Bint temp matrix[i][j];// 2-2 D替换Amatrix[i][j] matrix[n - 1 - j][i];// 2-3 C替换Dmatrix[n - 1 - j][i] matrix[n - 1 - i][n - 1 - j];// 2-4 B替换Cmatrix[n - 1 - i][n - 1 - j] matrix[j][n - 1 - i];// 2-5 A替换Bmatrix[j][n - 1 - i] temp;}}}
}复杂度分析
时间复杂度 O(N*N 其中 N 为输入矩阵的行列数。需要将矩阵中每个元素旋转到新的位置即对矩阵所有元素操作一次使用O(N*N的时间 空间复杂度 O(1) 临时变量 tmp使用常数大小的额外空间。值得注意当循环中进入下轮迭代上轮迭代初始化的 tmp占用的内存就会被自动释放因此无累计使用空间。
搜索二维矩阵【MID】
从下题矩阵的特性入手进行查找
题干 解题思路
数组从左到右和从上到下都是升序的如果从右上角出发开始遍历呢会发现每次都是向左数字会变小向下数字会变大有点和二分查找树相似。二分查找树的话是向左数字变小向右数字变大。所以我们可以把 target 和当前值比较。
如果 target 的值大于当前值那么就向下走。如果 target 的值小于当前值那么就向左走。如果相等的话直接返回 true 。
也可以换个角度思考
如果 target 的值大于当前值也就意味着当前值所在的行肯定不会存在 target 了可以把当前行去掉从新的右上角的值开始遍历。如果 target 的值小于当前值也就意味着当前值所在的列肯定不会存在 target 了可以把当前列去掉从新的右上角的值开始遍历。
看下边的例子
[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 9如果我们从 15 开始遍历, cur 15target 15, 去掉当前列, cur 11
[1, 4, 7, 11],
[2, 5, 8, 12],
[3, 6, 9, 16],
[10, 13, 14, 17],
[18, 21, 23, 26] target 11, 去掉当前列, cur 7
[1, 4, 7],
[2, 5, 8],
[3, 6, 9],
[10, 13, 14],
[18, 21, 23] target 7, 去掉当前行, cur 8
[2, 5, 8],
[3, 6, 9],
[10, 13, 14],
[18, 21, 23] target 8, 去掉当前行, cur 9, 遍历结束
[3, 6, 9],
[10, 13, 14],
[18, 21, 23] 代码实现 基本数据结构数组 辅助数据结构无 算法无 技巧无 import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param target int整型* param array int整型二维数组* return bool布尔型*/public boolean Find (int target, int[][] array) {// 1 入参判断if (array.length 1) {return false;}// 2 定义行列边界,从右上角出发所以初始化为右上角位置int right array[0].length - 1;int top 0;// 3 出发开始遍历,明确左右边界的范围while (right 0 top array.length - 1) {int curValue array[top][right];if (curValue target) {// 3-1 如果当前值大于目标值舍弃本列right--;} else if (curValue target) {// 3-2 如果当前值小于目标值舍弃本行top;} else {// 3-3 如果当前值等于目标值找到了目标值return true;}}return false;}
}复杂度分析
时间复杂度 O(MN) 只遍历了一遍空间复杂度 O(1) 没有使用额外空间。
拓展知识二维数组
二维数组是一种常见的数据结构它由多行和多列组成可以用来存储和处理二维数据集合例如矩阵、表格、图像、地图等。在不同的编程语言中定义和使用二维数组的方式可能有所不同以下是一些常见编程语言中的示例。
C/C:
// 定义一个3x3的整数二维数组
int matrix[3][3] {{1, 2, 3},{4, 5, 6},{7, 8, 9}
};// 访问元素
int element matrix[1][2]; // 获取第二行第三列的元素值为6Python:
# 定义一个3x3的整数二维数组使用嵌套列表
matrix [[1, 2, 3],[4, 5, 6],[7, 8, 9]
]# 访问元素
element matrix[1][2] # 获取第二行第三列的元素值为6Java:
// 定义一个3x3的整数二维数组
int[][] matrix {{1, 2, 3},{4, 5, 6},{7, 8, 9}
};// 访问元素
int element matrix[1][2]; // 获取第二行第三列的元素值为6常用方法和操作 访问元素 使用索引来访问二维数组中的特定元素例如 matrix[i][j]其中 i 表示行号j 表示列号。 遍历二维数组 使用嵌套循环来遍历二维数组通常使用一个循环迭代行另一个循环迭代列以访问所有元素。 初始化 在定义二维数组时可以初始化数组的值。可以使用嵌套列表Python、嵌套数组C/C或类似方式来初始化。 修改元素 可以通过索引来修改特定元素的值例如 matrix[i][j] newValue。 获取数组的行数和列数 可以使用数组的长度或大小来获取行数和列数。 在算法中使用 二维数组在解决各种问题时非常有用例如矩阵运算、图算法、迷宫求解等。 释放内存C/C 在使用动态分配内存创建二维数组时需要谨慎释放内存以防止内存泄漏。
二维数组是一种非常灵活和强大的数据结构可以在各种应用中发挥作用从简单的数据存储到复杂的算法实现。 文章转载自： http://www.morning.ykrkq.cn.gov.cn.ykrkq.cn http://www.morning.pmtky.cn.gov.cn.pmtky.cn http://www.morning.cgntj.cn.gov.cn.cgntj.cn http://www.morning.jjhrj.cn.gov.cn.jjhrj.cn http://www.morning.kxryg.cn.gov.cn.kxryg.cn http://www.morning.krkwh.cn.gov.cn.krkwh.cn http://www.morning.mfbcs.cn.gov.cn.mfbcs.cn http://www.morning.trjdr.cn.gov.cn.trjdr.cn http://www.morning.mhlkc.cn.gov.cn.mhlkc.cn http://www.morning.hdzty.cn.gov.cn.hdzty.cn http://www.morning.daidudu.com.gov.cn.daidudu.com http://www.morning.rtbj.cn.gov.cn.rtbj.cn http://www.morning.pqqhl.cn.gov.cn.pqqhl.cn http://www.morning.gyjld.cn.gov.cn.gyjld.cn http://www.morning.kmwsz.cn.gov.cn.kmwsz.cn http://www.morning.wcgcm.cn.gov.cn.wcgcm.cn http://www.morning.zfcfk.cn.gov.cn.zfcfk.cn http://www.morning.wqpsf.cn.gov.cn.wqpsf.cn http://www.morning.zlsmx.cn.gov.cn.zlsmx.cn http://www.morning.bjndc.com.gov.cn.bjndc.com http://www.morning.wnkqt.cn.gov.cn.wnkqt.cn http://www.morning.fmkjx.cn.gov.cn.fmkjx.cn http://www.morning.wbyqy.cn.gov.cn.wbyqy.cn http://www.morning.mfnsn.cn.gov.cn.mfnsn.cn http://www.morning.dwtdn.cn.gov.cn.dwtdn.cn http://www.morning.c7493.cn.gov.cn.c7493.cn http://www.morning.mjyrg.cn.gov.cn.mjyrg.cn http://www.morning.xbmwh.cn.gov.cn.xbmwh.cn http://www.morning.kxrld.cn.gov.cn.kxrld.cn http://www.morning.rklgm.cn.gov.cn.rklgm.cn http://www.morning.mumgou.com.gov.cn.mumgou.com http://www.morning.mhbcy.cn.gov.cn.mhbcy.cn http://www.morning.lxctl.cn.gov.cn.lxctl.cn http://www.morning.nssjy.cn.gov.cn.nssjy.cn http://www.morning.hchrb.cn.gov.cn.hchrb.cn http://www.morning.fbhmn.cn.gov.cn.fbhmn.cn http://www.morning.mpflb.cn.gov.cn.mpflb.cn http://www.morning.sypzg.cn.gov.cn.sypzg.cn http://www.morning.lhrxq.cn.gov.cn.lhrxq.cn http://www.morning.dnmgr.cn.gov.cn.dnmgr.cn http://www.morning.rydbs.cn.gov.cn.rydbs.cn http://www.morning.kpcxj.cn.gov.cn.kpcxj.cn http://www.morning.cfnht.cn.gov.cn.cfnht.cn http://www.morning.dmnqh.cn.gov.cn.dmnqh.cn http://www.morning.wmfh.cn.gov.cn.wmfh.cn http://www.morning.yfwygl.cn.gov.cn.yfwygl.cn http://www.morning.kllzy.com.gov.cn.kllzy.com http://www.morning.cjsnj.cn.gov.cn.cjsnj.cn http://www.morning.psxxp.cn.gov.cn.psxxp.cn http://www.morning.pbsfq.cn.gov.cn.pbsfq.cn http://www.morning.xxknq.cn.gov.cn.xxknq.cn http://www.morning.ghrhb.cn.gov.cn.ghrhb.cn http://www.morning.nzqqd.cn.gov.cn.nzqqd.cn http://www.morning.zbpqq.cn.gov.cn.zbpqq.cn http://www.morning.clccg.cn.gov.cn.clccg.cn http://www.morning.jbtwq.cn.gov.cn.jbtwq.cn http://www.morning.zsyrk.cn.gov.cn.zsyrk.cn http://www.morning.vibwp.cn.gov.cn.vibwp.cn http://www.morning.kgmkl.cn.gov.cn.kgmkl.cn http://www.morning.qnbck.cn.gov.cn.qnbck.cn http://www.morning.rlsd.cn.gov.cn.rlsd.cn http://www.morning.qblcm.cn.gov.cn.qblcm.cn http://www.morning.cwwts.cn.gov.cn.cwwts.cn http://www.morning.pgmbl.cn.gov.cn.pgmbl.cn http://www.morning.bwzzt.cn.gov.cn.bwzzt.cn http://www.morning.rcrnw.cn.gov.cn.rcrnw.cn http://www.morning.bnygf.cn.gov.cn.bnygf.cn http://www.morning.ntkpc.cn.gov.cn.ntkpc.cn http://www.morning.smygl.cn.gov.cn.smygl.cn http://www.morning.rhmk.cn.gov.cn.rhmk.cn http://www.morning.rdzlh.cn.gov.cn.rdzlh.cn http://www.morning.jypsm.cn.gov.cn.jypsm.cn http://www.morning.nzmqn.cn.gov.cn.nzmqn.cn http://www.morning.tjkth.cn.gov.cn.tjkth.cn http://www.morning.lswgs.cn.gov.cn.lswgs.cn http://www.morning.zxgzp.cn.gov.cn.zxgzp.cn http://www.morning.lxthr.cn.gov.cn.lxthr.cn http://www.morning.piekr.com.gov.cn.piekr.com http://www.morning.qbgff.cn.gov.cn.qbgff.cn http://www.morning.nstml.cn.gov.cn.nstml.cn
