矩阵Zig-Zag遍历：对角线路径的优雅实现

矩阵Zig-Zag遍历对角线路径的优雅实现最近刷题遇到一个很有意思的矩阵遍历问题如何以Zig-Zag之字形的方式打印一个二维矩阵什么是Zig-Zag遍历简单来说就是从矩阵的左上角开始沿着对角线方向来回穿梭最终遍历所有元素。就像蛇形走位一样方向不断变化。示例1输入 1 2 3 4 5 6 7 8 9 输出1 2 4 7 5 3 6 8 9示例2输入 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 输出1 2 5 9 6 3 4 7 10 13 14 11 8 12 15 16核心思路这个问题的关键在于对角线遍历。我们维护两个指针行和列通过一个布尔变量来控制移动方向当row_inc true时我们向右上方移动行减1列加1当row_inc false时我们向左下方移动行加1列减1整个过程分为两个阶段前半部分从左上角到主对角线后半部分从主对角线到右下角矩阵的Zig-Zag遍历对角线路径的优雅实现听起来是不是有点绕别怕理解这类抽象算法光靠脑补图表太吃力了。强烈安利一个宝藏网站——图码它把超过60种数据结构和算法做成交互式动画可视化矩阵遍历的过程一目了然。更绝的是你不仅能输入自定义数据生成动画还能上传C/C/Java/Python代码进行可视化解析。无论是备战408考研还是应付数据结构期末考试它都能帮你把抽象逻辑拆解得明明白白。赶紧去图码体验一下让算法学习不再靠想象图码-数据结构与算法交互式可视化平台访问网站https://totuma.cn代码实现Python版defzig_zag_matrix(mat):nlen(mat)mlen(mat[0])row0col0row_incFalse# 打印前半部分mnmin(m,n)forlengthinrange(1,mn1):foriinrange(length):print(mat[row][col],end )ifi1length:breakifrow_inc:row1col-1else:row-1col1iflengthmn:breakifrow_inc:row1row_incFalseelse:col1row_incTrue# 调整位置开始后半部分ifrow0:ifcolm-1:row1else:col1row_incTrueelse:ifrown-1:col1else:row1row_incFalse# 打印后半部分MAXmax(m,n)-1fordiaginrange(MAX,0,-1):lengthmnifdiagmnelsediagforiinrange(length):print(mat[row][col],end )ifi1length:breakifrow_inc:row1col-1else:col1row-1ifrow0orcolm-1:ifcolm-1:row1else:col1row_incTrueelifcol0orrown-1:ifrown-1:col1else:row1row_incFalse复杂度分析时间复杂度O(n × m)每个元素只被访问一次空间复杂度O(1)只用了几个变量小技巧边界处理在切换方向时要特别注意矩阵的边界情况防止索引越界方向控制用一个布尔变量来控制移动方向比用两个变量更简洁对角线长度前半部分对角线长度递增后半部分递减总结矩阵的Zig-Zag遍历是一个经典的面试题考察的是对二维数组遍历的灵活运用。掌握了这种对角线遍历的思路你就能轻松应对类似的矩阵遍历问题啦快去试试吧动手写一遍才能真正理解其中的奥妙哦