指定されたアレイからスパイラル行列を作成します
を含む整数アレイが与えられた M × N
要素、構築 M × N
スパイラル順にそれから行列。
例えば、
Input: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Output:
[ 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 ]
Output:
[ 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 ]
この問題は、主に次の問題の逆です。
考え方は同じです。指定されたアレイから要素を1つずつ読み取り、行列をらせん状に埋めます。スパイラルの順序を維持するために、それぞれマトリックスの上部、右、下部、および左隅に4つのループが使用されます。
以下は、上記のアイデアに基づくC++、Java、およびPythonでの実装です。
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include <iostream> #include <iomanip> #include <cmath> #include <vector> using namespace std; //指定されたアレイからスパイラル行列を作成します vector<vector<int>> printSpiralOrder(vector<int> const &arr, int M, int N) { vector<vector<int>> mat; // 規範事例 if (arr.size() == 0) { return mat; } //`M × N`行列を作成します mat.resize(N, vector<int>(M)); int top = 0, bottom = M - 1; int left = 0, right = N - 1; int index = 0; while (1) { if (left > right) { break; } //一番上の行を印刷します for (int i = left; i <= right; i++) { mat[top][i] = arr[index++]; } top++; if (top > bottom) { break; } //右の列を印刷します for (int i = top; i <= bottom; i++) { mat[i][right] = arr[index++]; } right--; if (left > right) { break; } //一番下の行を印刷します for (int i = right; i >= left; i--) { mat[bottom][i] = arr[index++]; } bottom--; if (top > bottom) { break; } //左の列を印刷します for (int i = bottom; i >= top; i--) { mat[i][left] = arr[index++]; } left++; } } int main() { //`M × N`行列 int M = 5; int N = 5; //サイズ`M×N`のvector vector<int> arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 }; vector<vector<int>> matrix = printSpiralOrder(arr, M, N); for (auto &row: matrix) { for (auto &i: row) { cout << setw(3) << i; } cout << endl; } return 0; } |
出力:
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
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
import java.util.Arrays; class Main { //指定されたアレイからスパイラル行列を作成します private static int[][] printSpiralOrder(int[] arr, int M, int N) { // 規範事例 if (arr == null) { return null; } //`M × N`行列を作成します int[][] mat = new int[M][N]; int top = 0, bottom = M - 1; int left = 0, right = N - 1; int index = 0; while (true) { if (left > right) { break; } //一番上の行を印刷します for (int i = left; i <= right; i++) { mat[top][i] = arr[index++]; } top++; if (top > bottom) { break; } //右の列を印刷します for (int i = top; i <= bottom; i++) { mat[i][right] = arr[index++]; } right--; if (left > right) { break; } //一番下の行を印刷します for (int i = right; i >= left; i--) { mat[bottom][i] = arr[index++]; } bottom--; if (top > bottom) { break; } //左の列を印刷します for (int i = bottom; i >= top; i--) { mat[i][left] = arr[index++]; } left++; } return mat; } public static void main(String[] args) { //`M × N`行列 int M = 5; int N = 5; //サイズ`M×N`のアレイ int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 }; int[][] mat = printSpiralOrder(arr, M, N); for (var r: mat) { System.out.println(Arrays.toString(r)); } } } |
出力:
[ 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]
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#指定されたリストからスパイラル行列を作成します def printSpiralOrder(A, M, N): #ベースケース if not A: return [] top = left = 0 bottom = M - 1 right = N - 1 #は`M × N`行列を構築します mat = [[0 for x in range(N)] for y in range(M)] index = 0 while True: if left > right: break #は一番上の行を印刷します for i in range(left, right + 1): mat[top][i] = A[index] index = index + 1 top = top + 1 if top > bottom: break #右列を印刷 for i in range(top, bottom + 1): mat[i][right] = A[index] index = index + 1 right = right - 1 if left > right: break #印刷下段 for i in range(right, left - 1, -1): mat[bottom][i] = A[index] index = index + 1 bottom = bottom - 1 if top > bottom: break #左の列を印刷 for i in range(bottom, top - 1, -1): mat[i][left] = A[index] index = index + 1 left = left + 1 for r in mat: print(r) if __name__ == '__main__': #`M × N`マトリックス M = N = 5 #長さ`M×N`のリスト A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25] printSpiralOrder(A, M, N) |
出力:
[ 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]
提案されたソリューションの時間計算量は O(M × N) のために M × N
マトリックスであり、余分なスペースは必要ありません。
エクササイズ: 上記の問題の再帰的的な解決策を書いてください。