HJ35 蛇形矩阵

描述
蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。

例如，当输入5时，应该输出的三角形为：
1 3 6 10 15

2 5 9 14

4 8 13

7 12

11

输入描述：
输入正整数N（N不大于100）

输出描述：
输出一个N行的蛇形矩阵。

示例1

输入：
4
输出：
1 3 6 10
2 5 9
4 8
7

方法一：顺序填表

具体做法：

我们可以准备一个n∗n的二维矩阵，只填充矩阵上半个三角形，而填充顺序从每行的第一列开始，每次都往右上角方向填充元素，即矩阵行坐标递减，列坐标递增，而填充的数字依次增加就行了。

aaa.gif

然后我们顺序遍历这个矩阵，将非零的元素依次输出即可。

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int n; 
    while(cin >> n){
        vector<vector<int> > matrix(n, vector<int>(n, 0)); //定义一个n*n的矩阵
        int num = 1;
        for(int i = 0; i < n; i++){
            int j = i, k = 0;
            while(j >= 0){
                matrix[j][k] = num; //录入数字
                num++;
                j--; //往右上方移
                k++;
            }
        }
        for(int i = 0; i < n; i++){ //遍历数组每一行
            int j = 0;
            while( j < n && matrix[i][j] != 0){ //每行只输出前面非零部分
                cout << matrix[i][j] << " ";
                j++;
            }
            cout << endl; //换行
        }
    }
    return 0;
}

复杂度分析：

• 时间复杂度：O(n^2)，填充和输出矩阵都遍历n(n+1)/2个矩阵空间
• 空间复杂度：(n^2)，使用二维矩阵作为辅助数组

方法2：数学规律

具体做法：

仔细观察这样的蛇形矩阵，我们可以尝试找规律：

对于每一行第一个元素，我们发现2与1之间相差为1，4与2之间相差为2，7与4之间相差为3，11与7之间相差为4，则第iii行的第一个元素与它的下一行是相差了个行号（从1开始）。

对于每一行的每个元素，我们发现3与1之间相差为2，6与3之间相差为3，10与6之间相差为4，15与10之间相差为5，则第jjj列与它的前一列相差为其列号（从1开始）。

数学规律

有了这个规律，我们遍历这样的上三角形，对每个位置累加出数字即可。

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int n; 
    while(cin >> n){
        int k = 1; //起始元素为1
        for(int i = 1; i <= n; i++){ //遍历每一行
            cout << k << " ";  //输出每行首
            int temp = k;
            for(int j = i + 1; j <= n; j++){ //遍历本行的数
                temp += j; //每个数相差为j
                cout << temp << " ";
            }
            cout << endl;
            k += i; //下一行的首为这行首加上这行行号
        }
    }
    return 0;
}

复杂度分析：

• 时间复杂度：O(n^2)，还是要遍历n(n+1)/2n(n+1)/2n(n+1)/2个元素
• 空间复杂度：O(1)，无额外空间