题目描述
输入两个整数n和m,输出一个n行m列的矩阵,将数字 1 到 n*m 按照回字蛇形填充至矩阵中。
具体矩阵形式可参考样例。
输入格式
输入共一行,包含两个整数n和m。
输出格式
输出满足要求的矩阵。
矩阵占n行,每行包含m个空格隔开的整数。
数据范围
1≤n,m≤100
样例
输入样例:
3 3
输出样例:
1 2 3
8 9 4
7 6 5
算法1
(暴力枚举) $O(n^2)$
拿到这个题,我两个想法,要赋值进入数组,要么数组下标动,要么数字动
就是方法1:按照从1-N顺序输入,看每次输入的那个对应的下标
2:下标顺序来,每次计算应该输入什么
我选择了1
时间复杂度
参考文献
Java 代码
public class day3 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] arr = new int[n][m];
int num = 1;
//循环圈数
int times = m>n?(m+1)/2:(n+1)/2;
int i = 0,j=0;
int mn = m,mm = n;
for (int k = 0; k < times; k++) {
if (num<=(m*n)){
num = right(arr,i,j,mn,num);
//重新计算开始坐标,循环次数
i+=1;j=j+mn-1;mm-=1;
}
if (num<=(m*n)){
num = under(arr,i,j,mm,num);
j-=1;i=i+mm-1;mn-=1;
}
if (num<=(m*n)){
num = left(arr,i,j,mn,num);
i-=1;j=j-mn+1;mm-=1;
}
if (num<=(m*n)){
num = up(arr,i,j,mm,num);
j+=1;i=i-mm+1;mn-=1;
}
}
for (int k = 0; k < n; k++) {
for (int l = 0; l < m; l++) {
System.out.print(arr[k][l]);
if (l!=m-1){
System.out.print(" ");
}
}
System.out.println();
}
}
/**
* 向右移动
* @param arr 数组
* @param i 开始位置纵坐标
* @param j 开始位置横坐标
* @param times 偏移量
* @param num 要加的数据大小
* @return
*/
public static int right(int[][] arr,int i ,int j,int times,int num){
for (int k = 0; k <times; k++) {
arr[i][j++] = num++;
}
return num;
}
//下
public static int under(int[][] arr,int i ,int j,int times,int num){
for (int k = 0; k <times; k++) {
arr[i++][j] = num++;
}
return num;
}
//左
public static int left(int[][] arr,int i ,int j,int times,int num){
for (int k = 0; k <times; k++) {
arr[i][j--] = num++;
}
return num;
}
//上
public static int up(int[][] arr,int i ,int j,int times,int num){
for (int k = 0; k <times; k++) {
arr[i--][j] = num++;
}
return num;
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla