zigzag数组：输入n，求一个nXn矩阵，规定矩阵沿45度递增，形成一个zigzag数组

一时失言乱红尘 2022-08-06 12:19 15阅读 0赞

同样是找规律的[螺旋队列见这个帖子][Link 1]。

## 面试题目： ##

输入n，求一个nXn矩阵，规定矩阵沿45度递增，形成一个zigzag数组(JPEG编码里取像素数据的排列顺序)，请问如何用C++实现？

（中国台湾著名硬件公司2007年11月面试题）（自程序员面试宝典第四版92页）

看了网上的好几篇文章，由于本人 愚钝，未能理解，故自己认真想了想，总结如下。

对zigzag数组，可以理解为一个矩阵，分为两部分来解决：**右上部分和左下部分**。

## 数组下标 ##

图1 给出了一个n=7时候的矩阵的下标变化情况，例如“24”表示矩阵的第2行第4列（从0开始）。

![Center][] ![Center 1][]

## 右上部分    ##

右上部分数字依次增大的顺序如图2的红色箭头所示，该部分包括矩阵的对角线。

注意下面的分析中，最终的规律都要转化到下标上，因为该二维数组是和下标紧密相关的。

对右上部分来说：结合图1和图2可以看出几个规律：

（1）沿着红色箭头的方向，数组的值从0开始，每次加1，逐渐增大。

（2）每条红线上的下标之和均相等，例如第三条红线，下标和都是2；并且下标和从0开始，每次加1，依次增加。矩阵对角线的下标和是6。

（3）第零条红线上数字个数为一个（下标和为0），第一条红线上数字为2个（下标和为1），……，对角线为第六条红线，数字个数为七（下标和为6）。即：第s条红线上数字个数为s + 1个，s = 下标和。**设二维数组的某个下标为（i,j），那么下标和s = i + j**。

（4）**每条斜线上第一个数字（也是最小的数字）**是上一行最大数字加1。也**等于之前所有斜线上的数字的个数之和**，例如第四条斜线上第一个数组是6，它等于第一、二、三条斜线上的数字之和6。

（5）而每条斜线上数字个数是一个等差数列，第0斜线1个，第1斜线2个，……，第s斜线s + 1个。又因为 s = i + j ， 因此，前s条（从0条到第s-1条）斜线上一共有1 + 2 + ……+ s个数字，也就是s(s+1)/2个数字；转化为与下标相关：用下标表示(s= i+j)：s(s+1)/2。即，**下一斜线的第一个数字值就是s(s+1)/2**。

得到了每条斜线上第一个数字的值，那么该斜线上之后的每个值都是在这个值的基础上依次加1得到的。

（6）下标和为奇数时红线的箭头是向左下方的，且下标i是从0依次增大的；下标和为偶数时箭头是朝右上方的，且下标j是从0依次增大的。因此某斜线上的数字a\[i\]\[j\]可以表示如下：**当s % 2 != 0，即下标和为奇数时，表示为s(s+1)/2 + i；当s%2 ==0，即下标和为偶数时，表示为s(s+1)/2 + j**。

因此**某个位置上的值为s(s+1)/2 + ((i + j)%2 != 0 ? 0:1)**

（7）当下标和s 1等于输入的n - 1时，就是矩阵的对角线，这个作为**左上部分结束的条件**。

## 左下部分 ##

左下部分并不符合右上部分的规律，但该部分的规律也是十分明显的。该部分的图如下所示（在右侧同时给出了图2用于对比），图中显示的该部分相对于n\* n所应该减去的值，这里n\*n=7\*7= 49。例如最左侧第一条斜线上数字48 = n\*n - 1，所以图3该位置标为-1，这是为了方便找规律。

![Center 2][]![Center 3][]

左下部分从最左侧的斜线开始，也符合以下几个规律：

（1）该部分第一条斜线也是由一个元素组成，第二条斜线是由两个元素组成，……

（2）相对于n\*n所减去的值不断加1，因此，**该部分每个数字值都是n\*n减去某个有规律的数**。

根据右上部分的规律，也从只有一个元素的斜线来分析该部分：

将下标与斜线条数关联：

第s条（s大于等于0）斜线与下标i和j的关系：**s=2n - (i + j) - 2**。例如上图左下部分最长的斜线为第5条斜线：5 = 2\*7 - 7 - 2。

那么**第s条斜线左方所有的斜线上的数字个数之和D为D = 1+2+……+s = s(s+1)/2**。

第s条斜线上的第一个元素减去的值为s(s+1)/2 + 1，即D+1，第2个数为D+2，第k个数是D+k，即某斜线第k个数上减去的值为D + i，如何k跟下标发生关系呢？在右上部分时，这个1直接是与i或j相同，但这里分析图1并不能直接与i或j相关，分析可以得到k可以用**k = n - ((i + j)%2 != 0 ? i ： j)**来表示。

所以**某个位置上相对于n\*n减去的值是D +k = s(s+1)/2 + n - ((i + j)%2 != 0 ? i ： j)**，因此**某个位置上的值为n\*n - (D + k) = n\*n - \[s(s+1)/2 + n - ((i + j)%2 != 0 ? i ： j)\]。**

代码如下：

#include <stdio.h>
    #include <iostream>
    using namespace std;
    
    int **printnxn(int **pSpace,int N) {
    	int s,i,j;
    	int squa;
    	pSpace = (int **)malloc(N*sizeof(int *));      
    	if(pSpace == NULL)
    		return 0;
    	for(i=0; i<N; i++) { //注意这里的内存分配和释放
    		if ((pSpace[i] = (int *)malloc(N*sizeof(int))) == NULL) {
    			while (--i>0) {
    				free(pSpace[i]);
    			}
    			free(pSpace);
    			return 0;
    		}
    	}
    	squa = N*N;
    	for (i=0; i<N; i++) {
    		for (j=0; j<N; j++) {
    			s = i + j;
    			if (s<N)//解决右上部分，判断条件是下标和i+j小于输入的n
    			{
    				pSpace[i][j] = s*(s+1)/2 + (((i+j)%2 != 0) ? i : j);  //注释A
    			} 
    			else//解决右下部分
     			{
    				s = (N-1-i) + (N-1-j);
    				pSpace[i][j] = squa - s*(s+1)/2 -(N-(((i+j)%2 != 0)? i : j)); //注释B
     			}
     		}
    	}
    	for (i=0;i<N; i++) {
    		for (j=0; j<N; j++) {
    			 printf("%6d",pSpace[i][j]);
     		}
     		printf("\n");
     	}
     	return pSpace;
     }
    
    int main() { 	
    	int N;
    	scanf("%d",&N);
     	int **p;
     	printnxn(p,N);
    }

![Center 4][]

注：《程序员面试宝典》第93页该题的代码中，与上面代码注释A、B处的两行代码对应位置用了“==”，会得到下图所示的错误结果，与该书代码前边注释给出的示例数组不符。正确的应为上面代码注释A、B处那样为“!=”。上述文字已经给出了详细分析。

![Center 5][]

[Link 1]: http://blog.csdn.net/u013074465/article/details/43157737
[Center]: https://img-blog.csdn.net/20150123211545328?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMzA3NDQ2NQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 1]: /images/20220806/bd15b8d3bd0f466f870d5d5693cb9e72.png
[Center 2]: https://img-blog.csdn.net/20150125185746375?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMzA3NDQ2NQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 3]: /images/20220806/9e3508f936fe4d71ba9a21db1d0520ae.png
[Center 4]: /images/20220806/d70593a14efa4893ac489b0e899f7af7.png
[Center 5]: /images/20220806/c8e9149905b14e6b89489868ba3e65b5.png