7.矩阵的对角遍历分析.doc

矩阵的对角遍历分析 问题简介： ? ? 以对角线的方式从左至右或者从右至左的遍历一个矩阵。这个矩阵更确切的说是一个行和列都长度相等的方阵。比如说，我们按照从左到右，从上到下的方式遍历一个矩阵。如下图所示： 那么我们遍历的序列将如下：1, 2, 5, 3, 6, 9 4, 7, 10, 13, 8, 11, 14 12, 15, 16. 这是一个比较常见的问题。以前在一些面试中也碰到过。一般来说，只是顺序的遍历每行每列显得过于简单。而通过对角访问的时候，我们可以看到，对应要遍历的行数为矩阵行数的2倍减1. ? ? ? 以前面的问题为例，粗看如果要遍历对角的数据，需要首先从第一行开始，每一次找到在它左下角方向的元素，也就是假定取第一行的元素a[0][j]，则对应该序列后面的元素分别为a[1][i - 1], a[2][i-2]...a[i][0]。这样我们就遍历完了上面一半的内容，一直到右上到左下的对角线。 ? ? 遍历完了这部分之后我们就要从第一行的最后一列开始，一直到最右下角。每个序列每次行号增加1，列号减1，一直增加到最后一行。生成的序列应该类似如下：a[1][n-1], a[2][n-2]...a[n-1][1] 经过前面的讨论，我们可以得出如下部分的代码： ? Java代码?? public?static?void?traverseNoCopy(int[][]?a)?? {?? ????//?Traverse?the?upper?part?? ????for(int?j?=?0;?j??a[0].length;?j++)?? ????{?? ????????for(int?k?=?0;?k?=?j;?k++)?? ????????{?? ????????????System.out.print(a[k][j?-?k]?+??);?? ????????}?? ????????System.out.println();?? ????}?? ?? ????//?Traverse?the?lower?part?? ????for(int?i?=?1;?i??a.length;?i++)?? ????{?? ????????for(int?j?=?i;?j??a.length;?j++)?? ????????{?? ????????????System.out.print(a[j][a.length?-?j?+?i?-?1]?+??);?? ????????}?? ????????System.out.println();?? ????}?? }?? ?这个遍历的过程中，最难的地方是这个矩阵的遍历要分成两块，上面部分对应的二重循环中两个下标的关系和下面部分的不一样。要找到对应的关系则需要列出几个元素的序列来寻找其中的规律。 ? ?方法2： ? ? ? ? 和方法1比起来，这种方法需要占用额外的空间，但是相对来说更容易理解一点。我们看前面的矩阵图。当我们要从右上到左下遍历的时候，对应这个元素下面一行的元素是在它对应列元素左边一个。后面的元素依次类推。那么，既然如此，如果我们将每一行元素下面一行的元素依次向右移动一位，那该如何呢？这样，将构成一个如下图的样子： ? ? ? ? ? 一个有意思的地方就是，原来我们需要斜角去访问的地方，现在只需要逐列的访问就可以了。为了实现这么一个结构，我们需要额外构造一个2n -1维的矩阵，然后从左到右按列遍历矩阵就实现了同样的效果。根据这种思路，得到的代码如下： Java代码?? public?static?void?traverse(int[][]?a)?? {?? ????//?Suppose?we?traverse?from?left?to?right?and?from?upper?right?to?lower?left?? ????int[][]?b?=?new?int[a.length?*?2?-?1][a.length?*?2?-?1];?? ?? ????//?Copy?every?row?in?a?and?make?some?offset?accordingly?? ????for(int?i?=?0;?i??a.length;?i++)?? ????{?? ????????for(int?j?=?0;?j??a.length;?j++)?? ????????{?? ????????????b[i][i?+?j]?=?a[i][j];?? ????????}?? ????}?? ?? ????//?Traverse?every?column?from?left?to?right?? ????for(int?i?=?0;?i??b.length;?i++)?? ????{?? ?????