矩阵的对角遍历分析

问题简介：

    以对角线的方式从左至右或者从右至左的遍历一个矩阵。这个矩阵更确切的说是一个行和列都长度相等的方阵。比如说，我们按照从左到右，从上到下的方式遍历一个矩阵。如下图所示：

那么我们遍历的序列将如下：1, 2, 5, 3, 6, 9 4, 7, 10, 13, 8, 11, 14 12, 15, 16.

这是一个比较常见的问题。以前在一些面试中也碰到过。一般来说，只是顺序的遍历每行每列显得过于简单。而通过对角访问的时候，我们可以看到，对应要遍历的行数为矩阵行数的2倍减1.

 

问题分析：

方法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]

经过前面的讨论，我们可以得出如下部分的代码：

 

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维的矩阵，然后从左到右按列遍历矩阵就实现了同样的效果。根据这种思路，得到的代码如下：

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++)
	{
		for(int j = 0; j < b.length; j++)
		{
			if(b[j][i] != 0)
				System.out.print(b[j][i] + " ");
		}
		System.out.println();
	}
}

这种方式遍历的时候我们需要有一个假定，就是假设我们我们新构造的矩阵中，新增加的元素必须和原来矩阵中的元素不一样。否则按列遍历的时候会产生混淆。这里只是简单的用0来表示。具体实现的时候需要根据情况来调整。

总结：

        矩阵对角遍历的两种方法中，第一种方法的要点在于要根据遍历的顺序和方向来推断矩阵元素下标的变化规律。有时候找到这些规律会比较费时间一点。第二种方法则比较简单直观一些，首先推断出行之间元素的位置偏移，然后构造一个对应的偏移矩阵。这种方法的好处就是不需要费脑筋去推算下标变化的关系，之需要构造出来然后遍历就可以了。当然，这样做比较费空间，同时也需要保证元素的独特性以防止遍历的时候产生混淆。