漫画:如何螺旋遍历二维数组?

来自:CSDN 2020-10-01

以下文章来源于程序员小灰 ,作者小灰

作者 | 小灰

来源 | 程序员小灰(ID:chengxuyuanxiaohui)

第二天

什么意思呢?我们来举个例子,给定下面这样一个二维数组:

我们需要从左上角的元素 1 开始,按照顺时针进行螺旋遍历,一直遍历完所有的元素,遍历的路径就像下图一样:

经过这样的遍历,返回的元素结果如下:

1,2,3,4,5,10,15,20,19,18,17,16,11,6,7,8,9,14,13,12

公司

第 1 层

从左到右遍历 " 上边 ":

从上到下遍历 " 右边 ":

从右到左遍历 " 下边 ":

从下到上遍历 " 左边 ":

第 2 层

从左到右遍历 " 上边 ":

从上到下遍历 " 右边 ":

从右到左遍历 " 下边 ":

从下到上遍历 " 左边 ":

第 3 层

从左到右遍历 " 上边 ":

从上到下遍历 " 右边 ":

从右到左遍历 " 下边 ":

第三层的 " 左边 " 已无需遍历,二维数组到此遍历完毕。

public class SpiralOrder {

public static List<Integer> spiralOrder ( int [ ] [ ] matrix ) {

List<Integer> list = new ArrayList<Integer> ( ) ;

// 当二维数组是空或任何一个维度是 0,直接返回

if ( matrix == null || matrix.length == 0 || matrix [ 0 ] .length == 0 ) {

return list;

}

//m 是矩阵的行数

int m = matrix.length;

//n 是矩阵的列数

int n = matrix [ 0 ] .length;

// 大循环,从外向内逐层遍历矩阵

for ( int i=0; i< ( Math.min ( m, n ) +1 ) /2; i++ ) {

// 从左到右遍历 " 上边 "

for ( int j=i; j<n-i; j++ ) {

list.add ( matrix [ i ] [ j ] ) ;

}

// 从上到下遍历 " 右边 "

for ( int j=i+1; j<m-i; j++ ) {

list.add ( matrix [ j ] [ ( n-1 ) -i ] ) ;

}

// 从右到左遍历 " 下边 "

for ( int j=i+1; j<n-i; j++ ) {

list.add ( matrix [ ( m-1 ) -i ] [ ( n-1 ) -j ] ) ;

}

// 从下到上遍历 " 左边 "

for ( int j=i+1; j<m-1-i; j++ ) {

list.add ( matrix [ ( m-1 ) -j ] [ i ] ) ;

}

}

return list;

}

public static void main ( String [ ] args ) {

int [ ] [ ] matrix = {

{ 1, 2, 3, 4, 5 },

{ 6, 7, 8, 9, 10 },

{ 11, 12, 13, 14, 15 },

{ 16, 17, 18, 19, 20 }

};

int [ ] [ ] matrix2 = {

{ 1, 2, 3, 4, 5 },

{ 6, 7, 8, 9, 10 },

{ 11, 12, 13, 14, 15 },

{ 16, 17, 18, 19, 20 },

{ 21, 22, 23, 24, 25 }

};

List<Integer> resultList1 = spiralOrder ( matrix ) ;

System.out.println ( Arrays.toString ( resultList1.toArray ( ) ) ) ;

List<Integer> resultList2 = spiralOrder ( matrix2 ) ;

System.out.println ( Arrays.toString ( resultList2.toArray ( ) ) ) ;

}

}

在上面的代码中,一个大循环当中包含了 4 个小循环。大循环控制了每一层的遍历,4 个小循环分别实现了同一层上边、右边、下边,左边的遍历。

当遍历到最内层时,4 个小循环并不会全都执行,比如测试代码中 matrix2 的最内层只有一个元素 13,那么执行完第 1 个小循环,就不会再进入后面 3 个小循环:

更多精彩推荐

程序员删库被判 6 年,公司损失近亿,云原生时代如何打造安全防线?

腾讯回应 Wecom 是企业微信海外版;美国地方法院紧急叫停微信禁令;Vue 3 发布 | 极客头条

曾是谷歌程序员,抛下百万年薪创业,4 年成就 7 亿用户,今身价百亿!

首次在手机端不牺牲准确率实现 BERT 实时推理,比 TensorFlow-Lite 快近 8 倍,每帧只需 45ms

Service Mesh 在超大规模场景下的落地挑战

比特币背后的技术,是否已成为科技领军代表?

点分享

点点赞

点在看