スパイラルマトリクスのjava実装
面接ではこのような問題が発生し,正の整数nを入力して螺旋行列を実現する.
例えば入力5、出力
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
入力6、出力
1 2 3 4 5 6
20 21 22 23 24 7
19 32 33 34 25 8
18 31 36 35 26 9
17 30 29 28 27 10
16 15 14 13 12 11
当時兄は睡眠不足で、再帰アルゴリズムを使って出力し、実現できないことに気づいた.
後に数学モデルを構築し,完璧な数学式を得た.
まず、n=5、(1,3)が第1のリング、(1,5)が第1のリング、(2,3)が第2のリングでint k=min(min(i,j),min(n+1−i,j),min(i,n+1−j));
を選択します.第2ステップは、kリング前のk−1リングの和を決定し、最後に(i,j)がkリングのどちらにあるかを判断し、対応するステップ数加算を行う.
アルゴリズムの複雑さはo(n^2)であるが,アルゴリズムは比較的明瞭であり,もちろん構造法で行うこともできる.
10を入力すると、次の結果が得られます.
1 2 3 4 5 6 7 8 9 10
36 37 38 39 40 41 42 43 44 11
35 64 65 66 67 68 69 70 45 12
34 63 84 85 86 87 88 71 46 13
33 62 83 96 97 98 89 72 47 14
32 61 82 95 100 99 90 73 48 15
31 60 81 94 93 92 91 74 49 16
30 59 80 79 78 77 76 75 50 17
29 58 57 56 55 54 53 52 51 18
28 27 26 25 24 23 22 21 20 19
例えば入力5、出力
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
入力6、出力
1 2 3 4 5 6
20 21 22 23 24 7
19 32 33 34 25 8
18 31 36 35 26 9
17 30 29 28 27 10
16 15 14 13 12 11
当時兄は睡眠不足で、再帰アルゴリズムを使って出力し、実現できないことに気づいた.
後に数学モデルを構築し,完璧な数学式を得た.
package test;
public class Test {
public static void main(String[] args) {
printMatrix(6);
}
public static int min(int i,int j)
{
return i<=j?i:j;
}
//i,j ， i,j 1
//k (i,j) ， 1
public static void printMatrix(int n)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
int k=min(min(min(i,j),min(n+1-i,j)),min(i,n+1-j));
int sum=0;
if(k>1)
{
for(int v=1;v<k;v++)
sum=sum+4*(n+1-2*v);
}
if (i==k&&j>=k&&j<=n+1-k)
System.out.print(String.format("%5d",sum+j-k+1));
else if(j==n+1-k&&i>k&&i<=n+1-k)
System.out.print(String.format("%5d",sum+n+1-2*k+i-k+1));
else if(i==n+1-k&&j>=k&&j<n+1-k)
System.out.print(String.format("%5d",sum+2*(n+1-2*k)+n+2-k-j));
else if(j==k&&i>k&&i<n+1-k)
System.out.print(String.format("%5d",sum+3*(n+1-2*k)+n+2-k-i));
}
System.out.println();
}
}
}まず、n=5、(1,3)が第1のリング、(1,5)が第1のリング、(2,3)が第2のリングでint k=min(min(i,j),min(n+1−i,j),min(i,n+1−j));
を選択します.第2ステップは、kリング前のk−1リングの和を決定し、最後に(i,j)がkリングのどちらにあるかを判断し、対応するステップ数加算を行う.
アルゴリズムの複雑さはo(n^2)であるが,アルゴリズムは比較的明瞭であり,もちろん構造法で行うこともできる.
10を入力すると、次の結果が得られます.
1 2 3 4 5 6 7 8 9 10
36 37 38 39 40 41 42 43 44 11
35 64 65 66 67 68 69 70 45 12
34 63 84 85 86 87 88 71 46 13
33 62 83 96 97 98 89 72 47 14
32 61 82 95 100 99 90 73 48 15
31 60 81 94 93 92 91 74 49 16
30 59 80 79 78 77 76 75 50 17
29 58 57 56 55 54 53 52 51 18
28 27 26 25 24 23 22 21 20 19