螺旋输出行列为n的数组(数字范围1-n*n)

Posted on | | Visitors:

这道题是从朋友的面试经历中得知的，当时闲着没事就花点时间解决了，后来换了一个角度来看问题，又发现了另一个解法。很好！这个应该写在小本本上记下来。

常规思路

如果我们先在数组中找到1的位置，那么就可以按照题意在数组记录所有数字，最后输出遍历输出这个数组就行了。

通过观察发现：图中两个箭头就是计算一个方形数组的周期，从2开始的两个箭头就完成了2 X 2的数组计算，从5开始的两个箭头完成了3 X 3的数组计算，并且每个周期有两个拐弯的点。

由上面的分析，这里我们需要一个变量d来记录当前方向，以及一个变量l记录当前数组的行列长度。另外我们还需要计算出这两个拐弯的点，这里我们用ll表示上一数组的行列长度，这两个拐点分别是ll X ll + 1和 ll X ll + l。

接下来就可以写代码了，按照上面的分析来就能轻松搞定。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <math.h>

int a[1000][1000];
int n;
int dir[4][2] = {0,1,-1,0,0,-1,1,0};//方向向量

//在输出后面留空，这样方便查看。偷个懒，处理到三位数的情况就行了。
void myprint(int i, int j) {
    if (a[i][j] / 100) {
        printf("%d ",a[i][j]);
    }
    else if (a[i][j] / 10) {
        printf("%d  ",a[i][j]);
    }
    else {
        printf("%d   ",a[i][j]);
    }
}

int main(int argc, const char * argv[]) {
    while (scanf("%d",&n) != EOF) {
        memset(a, 0, sizeof(a));
        int px,py;
        //通过n的奇偶性来判断1的位置在哪儿
        if (n % 2 == 0) {
            px = n / 2;
            py = px - 1;
        }
        else {
            px = n / 2;
            py = px;
        }
        a[px][py] = 1;
        //数组行列长度
        int l = 1;
        //当前方向
        int d = 0;
        for (int i = 2; i <= n*n; i++) {
            px = px + dir[d][0];
            py = py + dir[d][1];
            a[px][py] = i;
            //i大于当前数组大小就更新当前数组行列长度
            if (i > l * l) {
                l++;
            }
            //判断当前是否处于拐点
            int ll2 = (l-1) * (l-1);
            if (i == ll2 + 1 || i == ll2 + l) {
                d++;
                d%=4;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                myprint(i, j);
            }
            printf("\n");
        }
    }
    return 0;
}

问题升级

虽然上面解决了这个问题，但是我们相当于遍历了两次数组，可不可以一次遍历完成输出呢？

遍历输出的顺序是从左往右，从上到下。从图中可以看出每行输出的时候，只要列值保持在对角线（以1为中心）的上下夹角范围（包括对角线上），在当前行满足递增或递减的规律；而列值保持在对角线的左右夹角范围（不包括对角线上），在当前列满足递增或递减的规律。

这个思路判断条件很多，注意去除掉冗余判断。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <math.h>

int a[1000][1000];
int n;

//在输出后面留空，这样方便查看。偷个懒，处理到三位数的情况就行了。
void myprint(int i, int j) {
    if (a[i][j] / 100) {
        printf("%d ",a[i][j]);
    }
    else if (a[i][j] / 10) {
        printf("%d  ",a[i][j]);
    }
    else {
        printf("%d   ",a[i][j]);
    }
}

int main(int argc, const char * argv[]) {
    while (scanf("%d",&n) != EOF) {
        memset(a, 0, sizeof(a));
        int px,py;
        //通过n的奇偶性来判断1的位置在哪儿
        if (n % 2 == 0) {
            px = n / 2;
            py = px - 1;
        }
        else {
            px = n / 2;
            py = px;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                //左对角线夹角
                if (j - py < -abs(i - px)) {
                    a[i][j] = a[i-1][j] + 1;
                }
                //计算上下对角线夹角的第一个值
                else if (j - py == -abs(i - px)) {
                    if (i - px <= 0) {
                        int tmp = 2*abs(j-py);
                        a[i][j] = tmp * tmp + 1;
                    }
                    else {
                        int tmp = 2*abs(j-py);
                        a[i][j] = tmp * tmp + 1 + tmp;
                    }
                }
                //从上下对角线夹角的第一个值开始递推
                else if (j - py > -abs( i-px ) && j - py <= abs(i - px)) {
                    if (i - px <= 0) {
                        //这里有越界情况，单独处理n为偶数的这种特殊情况
                        if (j-1 < 0) {
                            int tmp = 2*abs(i-px);
                            a[i][j] = tmp * tmp;
                        }
                        else {
                            a[i][j] = a[i][j-1] - 1;
                        }
                    }
                    else {
                        a[i][j] = a[i][j-1] + 1;
                    }
                }
                //右对角线夹角
                else {
                    a[i][j] = a[i-1][j] - 1;
                }
                myprint(i, j);
            }
            printf("\n");
        }
    }
    return 0;
}

提示：评论是disqus，需要使用请翻墙！