Home

LinkWorld Algorithm Blog

25 Sep 2019

二维数组Z型输出

将一个二维（$n×n$）的数组按照下面的顺序输出：

[[ 1.  3.  4. 10.]
 [ 2.  5.  9. 11.]
 [ 6.  8. 12. 15.]
 [ 7. 13. 14. 16.]]

按照垂直对角线的方式一行行的输出：

# 第一个是圈数，第二个是循环的圈的数据
1->1
2->2 3
3->4 5 6
4->7 8 9 10
5->11 12 13
6->14 15
7->16

分析

上述的问题可以先转换为下面Z型的输出模式：

[[ 1.  3.  6. 10.]
 [ 2.  5.  9. 13.]
 [ 4.  8. 12. 15.]
 [ 7. 11. 14. 16.]]

按照垂直对角线的方式一行行的输出：

1->1
2->2 3
3->4 5 6
4->7 8 9 10
5->11 12 13
6->14 15
7->16

这种分析方法的区别和题干的区别在于，题干是单数行是以对角线为参照，从右往左遍历，反之是从左往右遍历。上述方法采用的默认以对角线为参照，从左往右遍历，即先去掉了方向的问题。

由于这种输出方式强依赖与二维数组的索引，因此分析索引和我们循环次数的关系。下面的数据中，r表示循环的次数（默认从1开始），括号内是数据对应的索引，第三个参数数据序号（用于展示遍历的序号）。

r:1, (0, 0), 1

r:2, (1, 0), 2
r:2, (0, 1), 3

r:3, (2, 0), 4
r:3, (1, 1), 5
r:3, (0, 2), 6

r:4, (3, 0), 7
r:4, (2, 1), 8
r:4, (1, 2), 9
r:4, (0, 3), 10

r:5, (3, 1), 11
r:5, (2, 2), 12
r:5, (1, 3), 13

r:6, (3, 2), 14
r:6, (2, 3), 15

r:7, (3, 3), 16

从上面的数据中，我们可以看到r=1,2,3,4的括号内第二个数据为[0]、[0,1]、[0,1,2]、[0,1,2,3]，数据的个数分别为1、2、3、4，刚好和r一致，且都是从0开始递增。r=5,6,7的括号内的第二个数据为[1,2,3]、[2,3]、[3]，数据的个数分别为3、2、1；$r-n$的值分别为1、2、3，刚好与[1,2,3]、[2,3]、[3]的第一个元素一致，且1、2、3分别到n所包含（不包括n）的元素分别为[1,2,3]、[2,3]、[3]。

分析完括号内第二个元素与r、n的关系后，需要找出括号内第一个元素与r、n的关系。第一括号内元素为(A, B),通过简单的分析，可以得出$A=r-B-1$。

当有了思路之后，我们就可以根据这个题目实现题干的内容，根据r的奇偶性来选择遍历的方向。当r为偶数，从左往右遍历；反之，从右往左遍历。

代码实现

Python实现

import numpy as np


def main(n):
    result = np.zeros([n, n])
    print(result)

    # count是指计数，r是第几圈
    count = 1
    if 1 == n:
        result[0][0] = count
    else:
        # 上三角(1,2,3,4)
        for r in range(1, n + 1):
            for y in range(0, r):
                print("r:%s, (%s, %s), %s" % (r, r - 1 - y, y, count))
                # 判断遍历的方向
                if r % 2 == 0:
                    result[r - 1 - y][y] = count
                else:
                    result[y][r - 1 - y] = count
                count += 1
        # 下三角(5,6,7)
        for r in range(n + 1, 2 * n):
            for y in range(r - n, n):
                print("r:%s, (%s, %s), %s" % (r, r - 1 - y, y, count))
                # 判断遍历的方向
                if r % 2 == 0:
                    result[r - 1 - y][y] = count
                else:
                    result[y][r - 1 - y] = count
                count += 1

    print(result)


if __name__ == '__main__':
    main(4)

输出结果

# 初始结果
[[0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]]
# 遍历的过程
r:1, (0, 0), 1
r:2, (1, 0), 2
r:2, (0, 1), 3
r:3, (2, 0), 4
r:3, (1, 1), 5
r:3, (0, 2), 6
r:4, (3, 0), 7
r:4, (2, 1), 8
r:4, (1, 2), 9
r:4, (0, 3), 10
r:5, (3, 1), 11
r:5, (2, 2), 12
r:5, (1, 3), 13
r:6, (3, 2), 14
r:6, (2, 3), 15
r:7, (3, 3), 16
# 输出结果
[[ 1.  3.  4. 10.]
 [ 2.  5.  9. 11.]
 [ 6.  8. 12. 15.]
 [ 7. 13. 14. 16.]]

附录

这个算法重在分析思路上，╮(╯▽╰)╭

Til next time,
LinkWorld at 23:21

scribble
‹