2 차원 배열을 어떻게 회전합니까?
Raymond Chen의 게시물 에서 영감을 받아 4x4 2 차원 배열이 있다고 가정하고 90도 회전하는 함수를 작성하십시오. Raymond는 의사 코드의 솔루션에 연결하지만 실제 상황을보고 싶습니다.
[1][2][3][4]
[5][6][7][8]
[9][0][1][2]
[3][4][5][6]
된다 :
[3][9][5][1]
[4][0][6][2]
[5][1][7][3]
[6][2][8][4]
업데이트 : Nick의 대답이 가장 간단하지만 n ^ 2보다 더 나은 방법이 있습니까? 행렬이 10000x10000이면 어떻게 되나요?
여기 C #에 있습니다.
int[,] array = new int[4,4] {
{ 1,2,3,4 },
{ 5,6,7,8 },
{ 9,0,1,2 },
{ 3,4,5,6 }
};
int[,] rotated = RotateMatrix(array, 4);
static int[,] RotateMatrix(int[,] matrix, int n) {
int[,] ret = new int[n, n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
ret[i, j] = matrix[n - j - 1, i];
}
}
return ret;
}
O (n ^ 2) 시간 및 O (1) 공간 알고리즘 (해결 방법 및 손수건이없는 항목!)
+90까지 회전 :
- 바꾸어 놓다
- 각 행을 반대로
-90까지 회전 :
방법 1 :
- 바꾸어 놓다
- 각 열을 반대로
방법 2 :
- 각 행을 반대로
- 바꾸어 놓다
+180 회전
방법 1 : +90 두 번 회전
방법 2 : 각 행을 뒤집은 다음 각 열을 뒤집습니다 (조옮김)
-180으로 회전 :
방법 1 : -90 두 번 회전
방법 2 : 각 열을 뒤집은 다음 각 행을 뒤집습니다
방법 3 : +180만큼 회전
좀 더 자세하게 설명하고 싶습니다. 이 답변에서 핵심 개념이 반복되고 속도가 느리고 의도적으로 반복됩니다. 여기에 제공된 솔루션은 구문 적으로 가장 컴팩트하지는 않지만 매트릭스 회전이 무엇인지 및 구현 결과를 배우려는 사람들을 위해 고안되었습니다.
첫째, 행렬이란 무엇입니까? 이 답변의 목적을 위해, 행렬은 너비와 높이가 동일한 그리드입니다. 행렬의 너비와 높이는 다를 수 있지만 간단하게하기 위해이 자습서에서는 너비와 높이가 동일한 행렬 ( 제곱 행렬 ) 만 고려합니다 . 그리고 그렇습니다, 행렬 은 복수의 행렬입니다.
매트릭스의 예는 2 × 2, 3 × 3 또는 5 × 5이다. 또는 더 일반적으로, NxN. 2 × 2 = 4이므로 2 × 2 행렬은 4 제곱을 갖습니다. 5 × 5 = 25이므로 5 × 5 행렬에는 25 제곱이 있습니다. 각 사각형을 요소 또는 항목이라고합니다. .아래 다이어그램에서 각 요소를 마침표 ( )로 표시합니다.
2 × 2 매트릭스
. .
. .
3 × 3 매트릭스
. . .
. . .
. . .
4 × 4 매트릭스
. . . .
. . . .
. . . .
. . . .
행렬을 회전한다는 것은 무엇을 의미합니까? 2x2 행렬을 가져 와서 각 요소에 숫자를 넣어 회전을 관찰 해 봅시다.
0 1
2 3
이것을 90도 회전 시키면 다음과 같이됩니다.
2 0
3 1
우리는 문자 그대로 자동차의 핸들을 돌리는 것처럼 전체 매트릭스를 오른쪽으로 한 번 돌 렸습니다. 매트릭스를 오른쪽에 "팁"하는 것이 도움이 될 수 있습니다. 파이썬에서 행렬을 가져 와서 오른쪽으로 한 번 회전하는 함수를 작성하려고합니다. 함수 서명은 다음과 같습니다.
def rotate(matrix):
# Algorithm goes here.
행렬은 2 차원 배열을 사용하여 정의됩니다.
matrix = [
[0,1],
[2,3]
]
따라서 첫 번째 인덱스 위치는 행에 액세스합니다. 두 번째 인덱스 위치는 열에 액세스합니다.
matrix[row][column]
행렬을 인쇄하는 유틸리티 함수를 정의합니다.
def print_matrix(matrix):
for row in matrix:
print row
매트릭스를 회전시키는 한 가지 방법은 한 번에 레이어를 만드는 것입니다. 그러나 레이어는 무엇입니까? 양파를 생각하십시오. 양파의 레이어와 마찬가지로 각 레이어가 제거되면 중앙으로 이동합니다. 다른 유추는 Matryoshka 인형 또는 패스 소포 게임입니다.
행렬의 너비와 높이는 해당 행렬의 레이어 수를 나타냅니다. 각 레이어마다 다른 심볼을 사용합시다 :
2 × 2 행렬에는 1 개의 층이 있습니다
. .
. .
3 × 3 행렬에는 2 개의 층이 있습니다
. . .
. x .
. . .
4 × 4 매트릭스에는 2 개의 레이어가 있습니다
. . . .
. x x .
. x x .
. . . .
5 × 5 매트릭스에는 3 개의 레이어가 있습니다
. . . . .
. x x x .
. x O x .
. x x x .
. . . . .
6 × 6 매트릭스에는 3 개의 레이어가 있습니다
. . . . . .
. x x x x .
. x O O x .
. x O O x .
. x x x x .
. . . . . .
7 × 7 매트릭스에는 4 개의 레이어가 있습니다
. . . . . . .
. x x x x x .
. x O O O x .
. x O - O x .
. x O O O x .
. x x x x x .
. . . . . . .
행렬의 너비와 높이를 1 씩 증가시키는 것이 항상 레이어 수를 증가시키는 것은 아닙니다. 위의 행렬을 취하고 레이어와 치수를 표로하면 너비와 높이가 2 증가 할 때마다 레이어 수가 한 번 증가합니다.
+-----+--------+
| N×N | Layers |
+-----+--------+
| 1×1 | 1 |
| 2×2 | 1 |
| 3×3 | 2 |
| 4×4 | 2 |
| 5×5 | 3 |
| 6×6 | 3 |
| 7×7 | 4 |
+-----+--------+
그러나 모든 레이어를 회전 할 필요는 없습니다. 1x1 매트릭스는 회전 전후에 동일합니다. 중앙 1x1 레이어는 전체 행렬의 크기에 관계없이 회전 전후에 항상 동일합니다.
+-----+--------+------------------+
| N×N | Layers | Rotatable Layers |
+-----+--------+------------------+
| 1×1 | 1 | 0 |
| 2×2 | 1 | 1 |
| 3×3 | 2 | 1 |
| 4×4 | 2 | 2 |
| 5×5 | 3 | 2 |
| 6×6 | 3 | 3 |
| 7×7 | 4 | 3 |
+-----+--------+------------------+
N × N 행렬이 주어지면 회전해야하는 레이어 수를 프로그래밍 방식으로 어떻게 결정할 수 있습니까? 너비 또는 높이를 2로 나누고 나머지를 무시하면 다음과 같은 결과가 나타납니다.
+-----+--------+------------------+---------+
| N×N | Layers | Rotatable Layers | N/2 |
+-----+--------+------------------+---------+
| 1×1 | 1 | 0 | 1/2 = 0 |
| 2×2 | 1 | 1 | 2/2 = 1 |
| 3×3 | 2 | 1 | 3/2 = 1 |
| 4×4 | 2 | 2 | 4/2 = 2 |
| 5×5 | 3 | 2 | 5/2 = 2 |
| 6×6 | 3 | 3 | 6/2 = 3 |
| 7×7 | 4 | 3 | 7/2 = 3 |
+-----+--------+------------------+---------+
N/2회전해야하는 레이어 수와 어떻게 일치합니까? 때로는 회전 가능한 레이어의 수가 매트릭스의 총 레이어 수보다 적습니다. 이것은 가장 안쪽 층이 오직 하나의 요소 (즉, 1x1 매트릭스)로 형성되어 회전 될 필요가 없을 때 발생한다. 단순히 무시됩니다.
의심 할 여지없이 행렬을 회전시키기 위해 함수에이 정보가 필요하므로 지금 추가해 보겠습니다.
def rotate(matrix):
size = len(matrix)
# Rotatable layers only.
layer_count = size / 2
이제 레이어가 무엇이며 실제로 회전해야하는 레이어 수를 결정하는 방법을 알았습니다. 단일 레이어를 어떻게 분리하여 회전시킬 수 있습니까? 먼저, 가장 바깥 쪽 레이어에서 안쪽 레이어까지 매트릭스를 검사합니다. 5 × 5 매트릭스에는 총 3 개의 레이어와 회전이 필요한 2 개의 레이어가 있습니다.
. . . . .
. x x x .
. x O x .
. x x x .
. . . . .
먼저 열을 살펴 보겠습니다. 0에서 세기를 가정하면 가장 바깥층을 정의하는 열의 위치는 0과 4입니다.
+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
| | . . . . . |
| | . x x x . |
| | . x O x . |
| | . x x x . |
| | . . . . . |
+--------+-----------+
0과 4는 또한 가장 바깥 쪽 레이어의 행 위치입니다.
+-----+-----------+
| Row | |
+-----+-----------+
| 0 | . . . . . |
| 1 | . x x x . |
| 2 | . x O x . |
| 3 | . x x x . |
| 4 | . . . . . |
+-----+-----------+
너비와 높이가 동일하기 때문에 항상 그렇습니다. 따라서 레이어의 열 및 행 위치를 4 개가 아닌 2 개의 값으로 정의 할 수 있습니다.
두 번째 레이어로 안쪽으로 이동하면 열의 위치는 1과 3입니다. 그리고 맞습니다. 행과 동일합니다. 다음 레이어로 안쪽으로 이동할 때 행 및 열 위치를 늘리거나 줄여야한다는 것을 이해하는 것이 중요합니다.
+-----------+---------+---------+---------+
| Layer | Rows | Columns | Rotate? |
+-----------+---------+---------+---------+
| Outermost | 0 and 4 | 0 and 4 | Yes |
| Inner | 1 and 3 | 1 and 3 | Yes |
| Innermost | 2 | 2 | No |
+-----------+---------+---------+---------+
따라서 각 레이어를 검사하기 위해 가장 바깥 쪽 레이어에서 시작하여 안쪽으로 이동하는 카운터를 증가 및 감소시키는 루프가 필요합니다. 이것을 '레이어 루프'라고합니다.
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
print 'Layer %d: first: %d, last: %d' % (layer, first, last)
# 5x5 matrix
matrix = [
[ 0, 1, 2, 3, 4],
[ 5, 6, 6, 8, 9],
[10,11,12,13,14],
[15,16,17,18,19],
[20,21,22,23,24]
]
rotate(matrix)
위의 코드는 회전해야하는 레이어의 (행 및 열) 위치를 반복합니다.
Layer 0: first: 0, last: 4
Layer 1: first: 1, last: 3
이제 각 레이어의 행과 열 위치를 제공하는 루프가 있습니다. 변수 first와는 last첫 번째와 마지막 행과 열의 인덱스 위치를 식별합니다. 행 및 열 테이블을 다시 참조하십시오.
+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
| | . . . . . |
| | . x x x . |
| | . x O x . |
| | . x x x . |
| | . . . . . |
+--------+-----------+
+-----+-----------+
| Row | |
+-----+-----------+
| 0 | . . . . . |
| 1 | . x x x . |
| 2 | . x O x . |
| 3 | . x x x . |
| 4 | . . . . . |
+-----+-----------+
따라서 행렬의 레이어를 탐색 할 수 있습니다. 이제 레이어 내에서 탐색하는 방법이 필요하므로 해당 레이어 주위로 요소를 이동할 수 있습니다. 요소는 한 레이어에서 다른 레이어로 '점프'하지는 않지만 각 레이어 내에서 이동합니다.
레이어에서 각 요소를 회전하면 전체 레이어가 회전합니다. 행렬의 모든 레이어를 회전하면 전체 행렬이 회전합니다. 이 문장은 매우 중요하므로 계속 진행하기 전에 이해하기 위해 최선을 다하십시오.
이제 요소를 실제로 이동시키는 방법, 즉 각 요소를 회전 한 다음 레이어와 궁극적으로 행렬을 회전시키는 방법이 필요합니다. 간단하게하기 위해 회전 가능한 레이어가 하나 인 3x3 매트릭스로 되돌립니다.
0 1 2
3 4 5
6 7 8
레이어 루프는 첫 번째와 마지막 열뿐만 아니라 첫 번째와 마지막 열의 인덱스를 제공합니다.
+-----+-------+
| Col | 0 1 2 |
+-----+-------+
| | 0 1 2 |
| | 3 4 5 |
| | 6 7 8 |
+-----+-------+
+-----+-------+
| Row | |
+-----+-------+
| 0 | 0 1 2 |
| 1 | 3 4 5 |
| 2 | 6 7 8 |
+-----+-------+
행렬은 항상 정사각형이므로 두 개의 변수 만 필요 first하며 last인덱스 위치는 행과 열에 대해 동일하므로.
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
# Our layer loop i=0, i=1, i=2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
# We want to move within a layer here.
변수 first와 last는 행렬의 네 모서리를 쉽게 참조 할 수 있습니다. 모서리 자체는 ( first및 last변수의 빼기, 덧셈 또는 오프셋없이) 다양한 순열을 사용하여 정의 할 수 있기 때문입니다 .
+---------------+-------------------+-------------+
| Corner | Position | 3x3 Values |
+---------------+-------------------+-------------+
| top left | (first, first) | (0,0) |
| top right | (first, last) | (0,2) |
| bottom right | (last, last) | (2,2) |
| bottom left | (last, first) | (2,0) |
+---------------+-------------------+-------------+
이러한 이유로 우리는 바깥 쪽 네 모퉁이에서 회전을 시작합니다. 먼저 회전합니다. 로 강조 표시하겠습니다 *.
* 1 *
3 4 5
* 7 *
우리는 각각 *을 *오른쪽 으로 바꾸고 싶습니다 . 다음 first과 last같이 다양한 순열 만 사용하여 정의한 모서리를 인쇄 해 보겠습니다 .
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
top_left = (first, first)
top_right = (first, last)
bottom_right = (last, last)
bottom_left = (last, first)
print 'top_left: %s' % (top_left)
print 'top_right: %s' % (top_right)
print 'bottom_right: %s' % (bottom_right)
print 'bottom_left: %s' % (bottom_left)
matrix = [
[0, 1, 2],
[3, 4, 5],
[6, 7, 8]
]
rotate(matrix)
출력은 다음과 같아야합니다.
top_left: (0, 0)
top_right: (0, 2)
bottom_right: (2, 2)
bottom_left: (2, 0)
이제 레이어 루프 내에서 각 모서리를 쉽게 바꿀 수 있습니다.
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
top_left = matrix[first][first]
top_right = matrix[first][last]
bottom_right = matrix[last][last]
bottom_left = matrix[last][first]
# bottom_left -> top_left
matrix[first][first] = bottom_left
# top_left -> top_right
matrix[first][last] = top_left
# top_right -> bottom_right
matrix[last][last] = top_right
# bottom_right -> bottom_left
matrix[last][first] = bottom_right
print_matrix(matrix)
print '---------'
rotate(matrix)
print_matrix(matrix)
코너 회전 전의 행렬 :
[0, 1, 2]
[3, 4, 5]
[6, 7, 8]
코너 회전 후 매트릭스 :
[6, 1, 0]
[3, 4, 5]
[8, 7, 2]
큰! 행렬의 각 모서리를 성공적으로 회전했습니다. 그러나 각 레이어의 중간에있는 요소를 회전시키지 않았습니다. 분명히 레이어 내에서 반복하는 방법이 필요합니다.
문제는 지금까지 함수에서 유일한 루프 (레이어 루프)가 각 반복에서 다음 레이어로 이동한다는 것입니다. 행렬에는 회전 가능한 레이어가 하나만 있으므로 모서리 만 회전 한 후 레이어 루프가 종료됩니다. 더 큰 5x5 매트릭스 (두 레이어가 회전해야하는 경우)에 어떤 일이 발생하는지 살펴 보겠습니다. 기능 코드는 생략되었지만 위와 동일하게 유지됩니다.
matrix = [
[0, 1, 2, 3, 4],
[5, 6, 7, 8, 9],
[10, 11, 12, 13, 14],
[15, 16, 17, 18, 19],
[20, 21, 22, 23, 24]
]
print_matrix(matrix)
print '--------------------'
rotate(matrix)
print_matrix(matrix)
출력은 다음과 같습니다.
[20, 1, 2, 3, 0]
[ 5, 16, 7, 6, 9]
[10, 11, 12, 13, 14]
[15, 18, 17, 8, 19]
[24, 21, 22, 23, 4]
가장 바깥 쪽 레이어의 모서리가 회전 한 것은 놀라운 일이 아니지만 다음 레이어 (내부)의 모서리도 회전 한 것을 알 수 있습니다. 이것은 말이됩니다. 레이어를 탐색하고 각 레이어의 모서리를 회전시키는 코드를 작성했습니다. 이것은 진보처럼 느껴지지만 불행히도 우리는 물러서야합니다. 이전 (외부) 레이어가 완전히 회전 할 때까지 다음 레이어로 넘어가는 것은 좋지 않습니다. 즉, 레이어의 각 요소가 회전 될 때까지 모퉁이 만 회전해도 효과가 없습니다!
심호흡하십시오. 또 다른 루프가 필요합니다. 중첩 루프. 새로운 중첩 루프는 first및 last변수와 오프셋을 사용하여 레이어 내에서 탐색합니다. 이 새로운 루프를 '요소 루프'라고합니다. 요소 루프는 맨 위 행, 각 요소는 오른쪽 아래, 각 요소는 맨 아래 행, 각 요소는 왼쪽 위를 따라 각 요소를 방문합니다.
- 맨 위 행을 따라 앞으로 이동하려면 열 인덱스를 증가시켜야합니다.
- 오른쪽으로 이동하면 행 색인이 증가해야합니다.
- 아래쪽을 따라 뒤로 이동하면 열 인덱스가 감소해야합니다.
- 왼쪽으로 이동하면 행 인덱스가 감소해야합니다.
이것은 복잡하게 들리지만, 위의 목표를 달성하기 위해 증가 및 감소하는 횟수는 매트릭스의 4면 모두에서 동일하게 유지되기 때문에 쉬워졌습니다. 예를 들면 다음과 같습니다.
- 맨 위 행을 가로 질러 1 개의 요소를 이동하십시오.
- 한 요소를 오른쪽 아래로 이동하십시오.
- 맨 아래 행을 따라 1 개의 요소를 뒤로 이동하십시오.
- 한 요소를 왼쪽 위로 이동하십시오.
이는 레이어 내에서 이동하기 위해 firstand last변수 와 함께 단일 변수를 사용할 수 있음을 의미 합니다. 맨 위 행을 가로 질러 오른쪽 아래로 이동하려면 증분이 필요합니다. 바닥을 따라 뒤로 이동하고 왼쪽을 위로 이동하면 감소해야합니다.
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
# Move through layers (i.e. layer loop).
for layer in range(0, layer_count):
first = layer
last = size - first - 1
# Move within a single layer (i.e. element loop).
for element in range(first, last):
offset = element - first
# 'element' increments column (across right)
top_element = (first, element)
# 'element' increments row (move down)
right_side = (element, last)
# 'last-offset' decrements column (across left)
bottom = (last, last-offset)
# 'last-offset' decrements row (move up)
left_side = (last-offset, first)
print 'top: %s' % (top)
print 'right_side: %s' % (right_side)
print 'bottom: %s' % (bottom)
print 'left_side: %s' % (left_side)
이제 상단을 오른쪽에, 오른쪽을 하단에, 하단을 왼쪽에, 왼쪽을 상단에 지정하면됩니다. 이 모든 것을 종합하면 다음과 같은 이점이 있습니다.
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
for element in range(first, last):
offset = element - first
top = matrix[first][element]
right_side = matrix[element][last]
bottom = matrix[last][last-offset]
left_side = matrix[last-offset][first]
matrix[first][element] = left_side
matrix[element][last] = top
matrix[last][last-offset] = right_side
matrix[last-offset][first] = bottom
매트릭스가 주어지면 :
0, 1, 2
3, 4, 5
6, 7, 8
우리의 rotate기능은 다음과 같습니다.
6, 3, 0
7, 4, 1
8, 5, 2
파이썬 :
rotated = zip(*original[::-1]) # On Python 3, list(zip(*original[::-1]))
싼거 알아
그리고 시계 반대 방향으로 :
rotated_ccw = zip(*original)[::-1] # On Python 3, list(zip(*original))[::-1]
작동 방식 : (댓글로 요청)
zip(*original)목록에서 해당 목록을 새 목록으로 쌓아서 2D 배열의 축을 교체합니다. ( *연산자는 함수에 포함 된 목록을 인수로 분배하도록 지시합니다)
>>> zip(*[[1,2,3],[4,5,6],[7,8,9]])
[[1,4,7],[2,5,8],[3,6,9]]
[::-1]문 반전 배열 요소는 (참조하시기 바랍니다 조각을 확장 ).
>>> [[1,2,3],[4,5,6],[7,8,9]][::-1]
[[7,8,9],[4,5,6],[1,2,3]]
마지막으로 둘을 결합하면 회전 변환이 발생합니다.
배치 변경은 [::-1]다른 레벨의 매트릭스에서리스트를 반전시킵니다.
다음은 결과를 유지하기 위해 완전히 새로운 배열을 사용하는 대신 회전을 수행하는 것입니다. 배열의 초기화를 중단하고 인쇄했습니다. 이것은 정사각형 배열에서만 작동하지만 크기는 상관 없습니다. 메모리 오버 헤드는 배열의 한 요소 크기와 동일하므로 원하는만큼 배열을 회전 할 수 있습니다.
int a[4][4];
int n = 4;
int tmp;
for (int i = 0; i < n / 2; i++)
{
for (int j = i; j < n - i - 1; j++)
{
tmp = a[i][j];
a[i][j] = a[j][n-i-1];
a[j][n-i-1] = a[n-i-1][n-j-1];
a[n-i-1][n-j-1] = a[n-j-1][i];
a[n-j-1][i] = tmp;
}
}
여기에는 좋은 코드가 많이 있지만 기하학적으로 진행되는 것을 보여주기 위해 코드 논리를 조금 더 잘 이해할 수 있습니다. 여기에 내가 어떻게 접근 할 것인가가 있습니다.
우선,이 작업을 전치사와 혼동하지 마십시오.
기본 아이디어는 레이어로 취급하고 한 번에 한 레이어 씩 회전시키는 것입니다.
우리에게 4x4가 있다고 말해
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
시계 방향으로 90도 회전하면
13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4
분해 해 봅시다. 먼저 4 개의 모서리를 회전시킵니다
1 4
13 16
그런 다음 비스듬한 다이아몬드를 회전시킵니다.
2
8
9
15
두 번째로 치우친 다이아몬드
3
5
12
14
바깥 쪽 가장자리를 처리하므로 본질적으로 한 번에 하나의 껍질을
마지막으로 중간 정사각형 (또는 움직이지 않는 최종 요소 만 이상한 경우)
6 7
10 11
이제 각 레이어의 인덱스를 알아 내고 항상 가장 바깥 레이어로 작업한다고 가정합니다.
[0,0] -> [0,n-1], [0,n-1] -> [n-1,n-1], [n-1,n-1] -> [n-1,0], and [n-1,0] -> [0,0]
[0,1] -> [1,n-1], [1,n-2] -> [n-1,n-2], [n-1,n-2] -> [n-2,0], and [n-2,0] -> [0,1]
[0,2] -> [2,n-2], [2,n-2] -> [n-1,n-3], [n-1,n-3] -> [n-3,0], and [n-3,0] -> [0,2]
우리가 가장자리를 반쯤 지나갈 때까지 계속해서
일반적으로 패턴은
[0,i] -> [i,n-i], [i,n-i] -> [n-1,n-(i+1)], [n-1,n-(i+1)] -> [n-(i+1),0], and [n-(i+1),0] to [0,i]
이전 게시물에서 말했듯이 C #의 모든 코드는 모든 크기의 행렬에 대해 O (1) 행렬 회전을 구현합니다. 간결성과 가독성을 위해 오류 확인이나 범위 확인이 없습니다. 코드:
static void Main (string [] args)
{
int [,]
// create an arbitrary matrix
m = {{0, 1}, {2, 3}, {4, 5}};
Matrix
// create wrappers for the data
m1 = new Matrix (m),
m2 = new Matrix (m),
m3 = new Matrix (m);
// rotate the matricies in various ways - all are O(1)
m1.RotateClockwise90 ();
m2.Rotate180 ();
m3.RotateAnitclockwise90 ();
// output the result of transforms
System.Diagnostics.Trace.WriteLine (m1.ToString ());
System.Diagnostics.Trace.WriteLine (m2.ToString ());
System.Diagnostics.Trace.WriteLine (m3.ToString ());
}
class Matrix
{
enum Rotation
{
None,
Clockwise90,
Clockwise180,
Clockwise270
}
public Matrix (int [,] matrix)
{
m_matrix = matrix;
m_rotation = Rotation.None;
}
// the transformation routines
public void RotateClockwise90 ()
{
m_rotation = (Rotation) (((int) m_rotation + 1) & 3);
}
public void Rotate180 ()
{
m_rotation = (Rotation) (((int) m_rotation + 2) & 3);
}
public void RotateAnitclockwise90 ()
{
m_rotation = (Rotation) (((int) m_rotation + 3) & 3);
}
// accessor property to make class look like a two dimensional array
public int this [int row, int column]
{
get
{
int
value = 0;
switch (m_rotation)
{
case Rotation.None:
value = m_matrix [row, column];
break;
case Rotation.Clockwise90:
value = m_matrix [m_matrix.GetUpperBound (0) - column, row];
break;
case Rotation.Clockwise180:
value = m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column];
break;
case Rotation.Clockwise270:
value = m_matrix [column, m_matrix.GetUpperBound (1) - row];
break;
}
return value;
}
set
{
switch (m_rotation)
{
case Rotation.None:
m_matrix [row, column] = value;
break;
case Rotation.Clockwise90:
m_matrix [m_matrix.GetUpperBound (0) - column, row] = value;
break;
case Rotation.Clockwise180:
m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column] = value;
break;
case Rotation.Clockwise270:
m_matrix [column, m_matrix.GetUpperBound (1) - row] = value;
break;
}
}
}
// creates a string with the matrix values
public override string ToString ()
{
int
num_rows = 0,
num_columns = 0;
switch (m_rotation)
{
case Rotation.None:
case Rotation.Clockwise180:
num_rows = m_matrix.GetUpperBound (0);
num_columns = m_matrix.GetUpperBound (1);
break;
case Rotation.Clockwise90:
case Rotation.Clockwise270:
num_rows = m_matrix.GetUpperBound (1);
num_columns = m_matrix.GetUpperBound (0);
break;
}
StringBuilder
output = new StringBuilder ();
output.Append ("{");
for (int row = 0 ; row <= num_rows ; ++row)
{
if (row != 0)
{
output.Append (", ");
}
output.Append ("{");
for (int column = 0 ; column <= num_columns ; ++column)
{
if (column != 0)
{
output.Append (", ");
}
output.Append (this [row, column].ToString ());
}
output.Append ("}");
}
output.Append ("}");
return output.ToString ();
}
int [,]
// the original matrix
m_matrix;
Rotation
// the current view of the matrix
m_rotation;
}
좋아, 손을 올리면 회전 할 때 실제로 원래 배열을 수정하지 않습니다. 그러나 객체가 클래스의 클라이언트로 회전 된 것처럼 보이는 한 OO 시스템에서는 중요하지 않습니다. 현재 Matrix 클래스는 원래 배열 데이터에 대한 참조를 사용하므로 m1 값을 변경하면 m2 및 m3도 변경됩니다. 생성자를 약간 변경하면 새 배열을 만들고 값을 복사하여 정렬합니다.
데이터를 제자리에 회전시키는 것이 필요할 수 있지만 (물리적으로 저장된 표현을 업데이트하려면) 인터페이스 액세스에 간접 레이어를 추가하는 것이 더 간단하고 성능이 향상됩니다.
interface IReadableMatrix
{
int GetValue(int x, int y);
}
Matrix이 인터페이스를 이미 구현 한 경우 다음 과 같이 데코레이터 클래스 를 통해 회전 할 수 있습니다 .
class RotatedMatrix : IReadableMatrix
{
private readonly IReadableMatrix _baseMatrix;
public RotatedMatrix(IReadableMatrix baseMatrix)
{
_baseMatrix = baseMatrix;
}
int GetValue(int x, int y)
{
// transpose x and y dimensions
return _baseMatrix(y, x);
}
}
+ 90 / -90 / 180도 회전, 수평 / 수직 뒤집기 및 스케일링도이 방식으로 모두 달성 할 수 있습니다.
특정 시나리오에서 성능을 측정해야합니다. 그러나 O (n ^ 2) 연산은 이제 O (1) 호출로 대체되었습니다. 그것은 가상 메서드 호출 입니다 그래서 회전 배열 회전 후 사용 빈도에 따라 달라집니다, 직접 배열 액세스보다 느립니다. 한 번만 사용하면이 방법이 확실히 이길 것입니다. 회전 한 다음 장기 실행 시스템에서 며칠 동안 사용하면 전체 회전이 더 잘 수행 될 수 있습니다. 또한 선불 비용을 수락 할 수 있는지 여부에 따라 다릅니다.
모든 성능 문제와 마찬가지로 측정, 측정, 측정!
이것은 자바에서 더 나은 버전입니다 : 너비와 높이가 다른 행렬로 만들었습니다.
- h는 여기 회전 후 행렬의 높이입니다
- w는 회전 후 행렬의 너비입니다.
public int[][] rotateMatrixRight(int[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
int[][] ret = new int[h][w];
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
ret[i][j] = matrix[w - j - 1][i];
}
}
return ret;
}
public int[][] rotateMatrixLeft(int[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
int[][] ret = new int[h][w];
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
ret[i][j] = matrix[j][h - i - 1];
}
}
return ret;
}
이 코드는 Nick Berardi의 게시물을 기반으로합니다.
루비 방식 : .transpose.map &:reverse
이미 많은 답변이 있으며 O (1) 시간 복잡성을 주장하는 두 가지를 발견했습니다. 실제 O (1) 알고리즘은 그대로 배열 저장을두고 어떻게 인덱스의 요소를 변경하는 것입니다. 여기서 목표는 추가 메모리를 소비하지 않으며 데이터를 반복하는 데 추가 시간이 필요하지 않다는 것입니다.
90도, -90도 및 180도 회전은 2D 배열에 몇 개의 행과 열이 있는지 아는 한 수행 할 수있는 간단한 변환입니다. 벡터를 90도 회전하려면 축을 바꾸고 Y 축을 무효화하십시오. -90 도의 경우 축을 바꾸고 X 축을 무효화하십시오. 180 도의 경우 스왑하지 않고 두 축을 모두 부정합니다.
축을 독립적으로 부정함으로써 수평 및 / 또는 수직 미러링과 같은 추가 변환이 가능합니다.
예를 들어 접근 자 메서드를 통해 수행 할 수 있습니다. 아래 예제는 JavaScript 함수이지만 개념은 모든 언어에 동일하게 적용됩니다.
// Get an array element in column/row order
var getArray2d = function(a, x, y) {
return a[y][x];
};
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr.length; i++) {
for (var j = 0; j < newarr[0].length; j++) {
newarr[i][j] = getArray2d(arr, i, j);
}
}
console.log(newarr);// Get an array element rotated 90 degrees clockwise
function getArray2dCW(a, x, y) {
var t = x;
x = y;
y = a.length - t - 1;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = getArray2dCW(arr, i, j);
}
}
console.log(newarr);// Get an array element rotated 90 degrees counter-clockwise
function getArray2dCCW(a, x, y) {
var t = x;
x = a[0].length - y - 1;
y = t;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = getArray2dCCW(arr, i, j);
}
}
console.log(newarr);// Get an array element rotated 180 degrees
function getArray2d180(a, x, y) {
x = a[0].length - x - 1;
y = a.length - y - 1;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr.forEach(() => newarr.push(new Array(arr[0].length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = getArray2d180(arr, i, j);
}
}
console.log(newarr);이 코드는 중첩 배열의 배열을 가정합니다. 여기서 각 내부 배열은 행입니다.
이 방법을 사용하면 배열이 회전되거나 변형 된 것처럼 임의의 순서로도 요소를 읽거나 쓸 수 있습니다. 이제 참조로 호출 할 올바른 함수를 선택하면됩니다.
접근 자 방법을 통해 변형을 부가 적으로 (비파괴 적으로) 적용하도록 개념을 확장 할 수 있습니다. 임의의 각도 회전 및 스케일링 포함
두 사람이 이미 새로운 배열을 만드는 예를 들었습니다.
고려해야 할 몇 가지 사항 :
(a) 실제로 데이터를 이동하는 대신 단순히 "회전 된"배열을 순회합니다.
(b) 제자리에서 회전을하는 것은 약간 까다로울 수 있습니다. 약간의 흠집이 필요합니다 (아마도 한 행이나 열 크기와 거의 같음). 현재 위치 전치 ( http://doi.acm.org/10.1145/355719.355729 ) 에 대한 고대 ACM 문서가 있지만 예제 코드는 불쾌한 FORTRAN입니다.
추가:
http://doi.acm.org/10.1145/355611.355612 는 또 다른 우수한 위치 전치 알고리즘입니다.
Nick의 대답은 NxN이 아닌 작은 수정만으로 NxM 배열에서도 작동합니다.
string[,] orig = new string[n, m];
string[,] rot = new string[m, n];
...
for ( int i=0; i < n; i++ )
for ( int j=0; j < m; j++ )
rot[j, n - i - 1] = orig[i, j];
이것을 생각하는 한 가지 방법은 축의 중심 (0,0)을 왼쪽 위 모서리에서 오른쪽 위 모서리로 옮겼다는 것입니다. 당신은 단순히 하나에서 다른 것으로 바꾸고 있습니다.
시간-O (N), 우주-O (1)
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n / 2; i++) {
int last = n - 1 - i;
for (int j = i; j < last; j++) {
int top = matrix[i][j];
matrix[i][j] = matrix[last - j][i];
matrix[last - j][i] = matrix[last][last - j];
matrix[last][last - j] = matrix[j][last];
matrix[j][last] = top;
}
}
}
여기 내 Ruby 버전이 있습니다 (값은 동일하게 표시되지 않지만 설명대로 회전합니다).
def rotate(matrix)
result = []
4.times { |x|
result[x] = []
4.times { |y|
result[x][y] = matrix[y][3 - x]
}
}
result
end
matrix = []
matrix[0] = [1,2,3,4]
matrix[1] = [5,6,7,8]
matrix[2] = [9,0,1,2]
matrix[3] = [3,4,5,6]
def print_matrix(matrix)
4.times { |y|
4.times { |x|
print "#{matrix[x][y]} "
}
puts ""
}
end
print_matrix(matrix)
puts ""
print_matrix(rotate(matrix))
출력 :
1 5 9 3
2 6 0 4
3 7 1 5
4 8 2 6
4 3 2 1
8 7 6 5
2 1 0 9
6 5 4 3
여기에 자바에 의한 공간 내 회전 방법이 있습니다. 정사각형이 아닌 2D 배열의 경우 어쨌든 새 배열을 만들어야합니다.
private void rotateInSpace(int[][] arr) {
int z = arr.length;
for (int i = 0; i < z / 2; i++) {
for (int j = 0; j < (z / 2 + z % 2); j++) {
int x = i, y = j;
int temp = arr[x][y];
for (int k = 0; k < 4; k++) {
int temptemp = arr[y][z - x - 1];
arr[y][z - x - 1] = temp;
temp = temptemp;
int tempX = y;
y = z - x - 1;
x = tempX;
}
}
}
}
새 배열을 만들어 모든 크기의 2D 배열을 회전시키는 코드 :
private int[][] rotate(int[][] arr) {
int width = arr[0].length;
int depth = arr.length;
int[][] re = new int[width][depth];
for (int i = 0; i < depth; i++) {
for (int j = 0; j < width; j++) {
re[j][depth - i - 1] = arr[i][j];
}
}
return re;
}
자바 스크립트에서 딤플의 +90 의사 코드 구현 (예 : 각 행을 바꾸고 각 행을 뒤집 음) :
function rotate90(a){
// transpose from http://www.codesuck.com/2012/02/transpose-javascript-array-in-one-line.html
a = Object.keys(a[0]).map(function (c) { return a.map(function (r) { return r[c]; }); });
// row reverse
for (i in a){
a[i] = a[i].reverse();
}
return a;
}
당신은이 작업을 수행 할 수 있습니다 3 단계 :
1 ) 행렬이 있다고 가정
1 2 3
4 5 6
7 8 9
2 ) 행렬의 조옮김
1 4 7
2 5 8
3 6 9
3 ) 회전 행렬을 얻기 위해 행을 교환하십시오.
3 6 9
2 5 8
1 4 7
이에 대한 Java 소스 코드 :
public class MyClass {
public static void main(String args[]) {
Demo obj = new Demo();
/*initial matrix to rotate*/
int[][] matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
int[][] transpose = new int[3][3]; // matrix to store transpose
obj.display(matrix); // initial matrix
obj.rotate(matrix, transpose); // call rotate method
System.out.println();
obj.display(transpose); // display the rotated matix
}
}
class Demo {
public void rotate(int[][] mat, int[][] tran) {
/* First take the transpose of the matrix */
for (int i = 0; i < mat.length; i++) {
for (int j = 0; j < mat.length; j++) {
tran[i][j] = mat[j][i];
}
}
/*
* Interchange the rows of the transpose matrix to get rotated
* matrix
*/
for (int i = 0, j = tran.length - 1; i != j; i++, j--) {
for (int k = 0; k < tran.length; k++) {
swap(i, k, j, k, tran);
}
}
}
public void swap(int a, int b, int c, int d, int[][] arr) {
int temp = arr[a][b];
arr[a][b] = arr[c][d];
arr[c][d] = temp;
}
/* Method to display the matrix */
public void display(int[][] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
}
산출:
1 2 3
4 5 6
7 8 9
3 6 9
2 5 8
1 4 7
PHP :
<?php
$a = array(array(1,2,3,4),array(5,6,7,8),array(9,0,1,2),array(3,4,5,6));
$b = array(); //result
while(count($a)>0)
{
$b[count($a[0])-1][] = array_shift($a[0]);
if (count($a[0])==0)
{
array_shift($a);
}
}
?>
이것은 C, O (1) 메모리 복잡성에서 시계 방향으로 90도 회전하여 구현 한 것입니다.
#include <stdio.h>
#define M_SIZE 5
static void initMatrix();
static void printMatrix();
static void rotateMatrix();
static int m[M_SIZE][M_SIZE];
int main(void){
initMatrix();
printMatrix();
rotateMatrix();
printMatrix();
return 0;
}
static void initMatrix(){
int i, j;
for(i = 0; i < M_SIZE; i++){
for(j = 0; j < M_SIZE; j++){
m[i][j] = M_SIZE*i + j + 1;
}
}
}
static void printMatrix(){
int i, j;
printf("Matrix\n");
for(i = 0; i < M_SIZE; i++){
for(j = 0; j < M_SIZE; j++){
printf("%02d ", m[i][j]);
}
printf("\n");
}
printf("\n");
}
static void rotateMatrix(){
int r, c;
for(r = 0; r < M_SIZE/2; r++){
for(c = r; c < M_SIZE - r - 1; c++){
int tmp = m[r][c];
m[r][c] = m[M_SIZE - c - 1][r];
m[M_SIZE - c - 1][r] = m[M_SIZE - r - 1][M_SIZE - c - 1];
m[M_SIZE - r - 1][M_SIZE - c - 1] = m[c][M_SIZE - r - 1];
m[c][M_SIZE - r - 1] = tmp;
}
}
}
다음은 Java 버전입니다.
public static void rightRotate(int[][] matrix, int n) {
for (int layer = 0; layer < n / 2; layer++) {
int first = layer;
int last = n - 1 - first;
for (int i = first; i < last; i++) {
int offset = i - first;
int temp = matrix[first][i];
matrix[first][i] = matrix[last-offset][first];
matrix[last-offset][first] = matrix[last][last-offset];
matrix[last][last-offset] = matrix[i][last];
matrix[i][last] = temp;
}
}
}
이 방법은 먼저 가장 바깥 쪽 레이어를 회전 한 다음 순차적으로 내부 레이어로 이동합니다.
선형 관점에서 행렬을 고려하십시오.
1 2 3 0 0 1
A = 4 5 6 B = 0 1 0
7 8 9 1 0 0
이제 조옮김
1 4 7
A' = 2 5 8
3 6 9
그리고 B에서 A '또는 A'에서 B '의 동작을 고려하십시오.
각기:
7 4 1 3 6 9
A'B = 8 5 2 BA' = 2 5 8
9 6 3 1 4 7
이것은 모든 nxn 행렬에 대해 확장 가능합니다. 이 개념을 코드에 빠르게 적용하면 다음과 같습니다.
void swapInSpace(int** mat, int r1, int c1, int r2, int c2)
{
mat[r1][c1] ^= mat[r2][c2];
mat[r2][c2] ^= mat[r1][c1];
mat[r1][c1] ^= mat[r2][c2];
}
void transpose(int** mat, int size)
{
for (int i = 0; i < size; i++)
{
for (int j = (i + 1); j < size; j++)
{
swapInSpace(mat, i, j, j, i);
}
}
}
void rotate(int** mat, int size)
{
//Get transpose
transpose(mat, size);
//Swap columns
for (int i = 0; i < size / 2; i++)
{
for (int j = 0; j < size; j++)
{
swapInSpace(mat, i, j, size - (i + 1), j);
}
}
}
[n, m] 2D 배열을 오른쪽으로 90도 회전시키는 C # 코드
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace MatrixProject
{
// mattrix class
class Matrix{
private int rows;
private int cols;
private int[,] matrix;
public Matrix(int n){
this.rows = n;
this.cols = n;
this.matrix = new int[this.rows,this.cols];
}
public Matrix(int n,int m){
this.rows = n;
this.cols = m;
this.matrix = new int[this.rows,this.cols];
}
public void Show()
{
for (var i = 0; i < this.rows; i++)
{
for (var j = 0; j < this.cols; j++) {
Console.Write("{0,3}", this.matrix[i, j]);
}
Console.WriteLine();
}
}
public void ReadElements()
{
for (var i = 0; i < this.rows; i++)
for (var j = 0; j < this.cols; j++)
{
Console.Write("element[{0},{1}]=",i,j);
this.matrix[i, j] = Convert.ToInt32(Console.ReadLine());
}
}
// rotate [n,m] 2D array by 90 deg right
public void Rotate90DegRight()
{
// create a mirror of current matrix
int[,] mirror = this.matrix;
// create a new matrix
this.matrix = new int[this.cols, this.rows];
for (int i = 0; i < this.rows; i++)
{
for (int j = 0; j < this.cols; j++)
{
this.matrix[j, this.rows - i - 1] = mirror[i, j];
}
}
// replace cols count with rows count
int tmp = this.rows;
this.rows = this.cols;
this.cols = tmp;
}
}
class Program
{
static void Main(string[] args)
{
Matrix myMatrix = new Matrix(3,4);
Console.WriteLine("Enter matrix elements:");
myMatrix.ReadElements();
Console.WriteLine("Matrix elements are:");
myMatrix.Show();
myMatrix.Rotate90DegRight();
Console.WriteLine("Matrix rotated at 90 deg are:");
myMatrix.Show();
Console.ReadLine();
}
}
}
결과:
Enter matrix elements:
element[0,0]=1
element[0,1]=2
element[0,2]=3
element[0,3]=4
element[1,0]=5
element[1,1]=6
element[1,2]=7
element[1,3]=8
element[2,0]=9
element[2,1]=10
element[2,2]=11
element[2,3]=12
Matrix elements are:
1 2 3 4
5 6 7 8
9 10 11 12
Matrix rotated at 90 deg are:
9 5 1
10 6 2
11 7 3
12 8 4
For i:= 0 to X do For j := 0 to X do graphic[j][i] := graphic2[X-i][j]
X는 그래픽이있는 배열의 크기입니다.
#transpose는 Ruby의 Array 클래스의 표준 메소드이므로 다음과 같습니다.
% irb
irb(main):001:0> m = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]]
=> [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]]
irb(main):002:0> m.reverse.transpose
=> [[3, 9, 5, 1], [4, 0, 6, 2], [5, 1, 7, 3], [6, 2, 8, 4]]
: 구현은 n ^ 2 이항 C로 작성 기능 당신은 여기에서 볼 수있다 http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-transpose "클릭을 선택하여 "전환"옆에있는 소스 "를 전환합니다.
나는 O (n ^ 2) 솔루션보다 더 잘 기억하지만 특별히 구성된 행렬 (예를 들어 희소 행렬)에 대해서만
모든 M * N 매트릭스의 경우 시계 방향으로 90도 회전하는 C 코드
void rotateInPlace(int * arr[size][size], int row, int column){
int i, j;
int temp = row>column?row:column;
int flipTill = row < column ? row : column;
for(i=0;i<flipTill;i++){
for(j=0;j<i;j++){
swapArrayElements(arr, i, j);
}
}
temp = j+1;
for(i = row>column?i:0; i<row; i++){
for(j=row<column?temp:0; j<column; j++){
swapArrayElements(arr, i, j);
}
}
for(i=0;i<column;i++){
for(j=0;j<row/2;j++){
temp = arr[i][j];
arr[i][j] = arr[i][row-j-1];
arr[i][row-j-1] = temp;
}
}
}
다음은 C에서의 제자리 구현입니다.
void rotateRight(int matrix[][SIZE], int length) {
int layer = 0;
for (int layer = 0; layer < length / 2; ++layer) {
int first = layer;
int last = length - 1 - layer;
for (int i = first; i < last; ++i) {
int topline = matrix[first][i];
int rightcol = matrix[i][last];
int bottomline = matrix[last][length - layer - 1 - i];
int leftcol = matrix[length - layer - 1 - i][first];
matrix[first][i] = leftcol;
matrix[i][last] = topline;
matrix[last][length - layer - 1 - i] = rightcol;
matrix[length - layer - 1 - i][first] = bottomline;
}
}
}
다음은 C에서 2 단계 솔루션 인 행렬 90도 회전을 시도한 것입니다. 먼저 행렬을 제자리에 바꾼 다음 열을 바꿉니다.
#define ROWS 5
#define COLS 5
void print_matrix_b(int B[][COLS], int rows, int cols)
{
for (int i = 0; i <= rows; i++) {
for (int j = 0; j <=cols; j++) {
printf("%d ", B[i][j]);
}
printf("\n");
}
}
void swap_columns(int B[][COLS], int l, int r, int rows)
{
int tmp;
for (int i = 0; i <= rows; i++) {
tmp = B[i][l];
B[i][l] = B[i][r];
B[i][r] = tmp;
}
}
void matrix_2d_rotation(int B[][COLS], int rows, int cols)
{
int tmp;
// Transpose the matrix first
for (int i = 0; i <= rows; i++) {
for (int j = i; j <=cols; j++) {
tmp = B[i][j];
B[i][j] = B[j][i];
B[j][i] = tmp;
}
}
// Swap the first and last col and continue until
// the middle.
for (int i = 0; i < (cols / 2); i++)
swap_columns(B, i, cols - i, rows);
}
int _tmain(int argc, _TCHAR* argv[])
{
int B[ROWS][COLS] = {
{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}
};
matrix_2d_rotation(B, ROWS - 1, COLS - 1);
print_matrix_b(B, ROWS - 1, COLS -1);
return 0;
}
@ dagorym : 아, 남자. 나는 "지루하다, 무엇을 숙고 할 수 있을까"퍼즐로 이것에 매달렸다. 내 전치사 코드를 생각해 냈지만 내 것과 거의 동일한 것을 발견하기 위해 여기에 도착했습니다 ... 아, 음. 여기는 루비입니다.
require 'pp'
n = 10
a = []
n.times { a << (1..n).to_a }
pp a
0.upto(n/2-1) do |i|
i.upto(n-i-2) do |j|
tmp = a[i][j]
a[i][j] = a[n-j-1][i]
a[n-j-1][i] = a[n-i-1][n-j-1]
a[n-i-1][n-j-1] = a[j][n-i-1]
a[j][n-i-1] = tmp
end
end
pp a
short normal[4][4] = {{8,4,7,5},{3,4,5,7},{9,5,5,6},{3,3,3,3}};
short rotated[4][4];
for (int r = 0; r < 4; ++r)
{
for (int c = 0; c < 4; ++c)
{
rotated[r][c] = normal[c][3-r];
}
}
간단한 C ++ 방법, 큰 배열에는 큰 메모리 오버 헤드가 있습니다.
참고 URL : https://stackoverflow.com/questions/42519/how-do-you-rotate-a-two-dimensional-array
'development' 카테고리의 다른 글
| Node.js (자바 스크립트)에서 어떻게 기다릴 수 있습니까? (0) | 2020.03.17 |
|---|---|
| NodeJ를 설치할 수 없습니다 : / usr / bin / env : node : 해당 파일 또는 디렉토리가 없습니다 (0) | 2020.03.17 |
| JPA hashCode () / equals () 딜레마 (0) | 2020.03.17 |
| Node.js / Express.js-app.router는 어떻게 작동합니까? (0) | 2020.03.17 |
| 병합 후 분기로 수행 할 작업 (0) | 2020.03.17 |