题目主要信息

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

2、多组样例输入

方法一：直接遍历输入

具体方法

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

C++代码

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

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

复杂度分析

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

方法二：找到规律

具体方法

• 找出规律即可，如实例输入4
  • 第一行：[1 3 6 10]
  • 第二行：去掉第一行的第一列，然后将后面的[3 6 10]分别减1得到的。
• 先构造第一行，根据规律求第2-n行
• 每一行处理后封装结果到 StringBuilder，注意空格和换行符

Java代码

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] nums = new int[n];
            StringBuilder result = new StringBuilder();
            for(int i = 0; i < n; i++) {
                // 先构造第一行
                if(i == 0) {
                    int addVal = 2;
                    nums[0] = 1;
                    for(int j = 1; j < n; j++) {
                        nums[j] = nums[j - 1] + addVal;
                        addVal++;
                    }
                } else {
                    // 从第二行开始构造每一列，遍历次数：(len-i)
                    for(int j = 1; j <= n - i; j++) {
                        nums[j - 1] = nums[j] - 1;
                    }
                }

                for(int k = 0; k < n - i; k++) {
                    result.append(nums[k] + " ");
                }
                result.append("\n");
            }
            System.out.println(result.toString().substring(0, result.length() - 1));
        }
    }

}

复杂度分析

• 时间复杂度：$O(n^2)O(n^2)$，遍历处理每一行每一列所需要的时间复杂度
• 空间复杂度：$O(n)O(n)$，维护了大小为n 的数组和结果字符串