2차원 배열을 어떻게 회전합니까?
https://stackoverflow.com/questions/42519
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
에서 영감을 받다 레이먼드 첸의 포스트, 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.또는 더 일반적으로는 N×N입니다.2×2 행렬은 2×2=4이므로 4개의 정사각형을 갖습니다.5×5 행렬은 5×5=25이므로 25개의 정사각형을 갖습니다.각 사각형을 요소 또는 항목이라고 합니다.각 요소를 마침표(.) 아래 다이어그램에서:
2×2 행렬
. .
. .
3×3 행렬
. . .
. . .
. . .
4×4 매트릭스
. . . .
. . . .
. . . .
. . . .
그렇다면 행렬을 회전시킨다는 것은 무엇을 의미하는가?2×2 행렬을 사용하고 회전을 관찰할 수 있도록 각 요소에 숫자를 입력해 보겠습니다.
0 1
2 3
이것을 90도 회전하면 다음과 같은 결과가 나옵니다.
2 0
3 1
우리는 문자 그대로 자동차의 핸들을 돌리는 것처럼 전체 매트릭스를 오른쪽으로 한 번 돌렸습니다.행렬을 오른쪽으로 "기울이는" 것을 생각하는 것이 도움이 될 수 있습니다.우리는 행렬을 받아 오른쪽으로 한 번 회전하는 함수를 Python으로 작성하고 싶습니다.함수 서명은 다음과 같습니다.
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
행렬을 회전하는 한 가지 방법은 한 번에 레이어별로 회전하는 것입니다.그런데 레이어란 무엇인가요?양파를 생각해 보세요.양파의 층과 마찬가지로 각 층이 제거되면 중앙으로 이동합니다.다른 비유는 마트료시카 인형 또는 소포 전달 게임.
행렬의 너비와 높이는 해당 행렬의 레이어 수를 나타냅니다.각 레이어에 대해 서로 다른 심볼을 사용해 보겠습니다.
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 |
+-----+--------+
그러나 모든 레이어를 회전해야 하는 것은 아닙니다.1×1 행렬은 회전 전후가 동일합니다.중앙 1×1 레이어는 전체 행렬의 크기에 관계없이 회전 전후에 항상 동일합니다.
+-----+--------+------------------+
| 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 회전해야 하는 레이어 수와 일치합니까?때때로 회전 가능한 레이어 수는 매트릭스의 전체 레이어 수에서 1을 뺀 값입니다.이는 가장 안쪽 레이어가 단 하나의 요소(예:1×1 행렬)이므로 회전할 필요가 없습니다.그냥 무시됩니다.
행렬을 회전하려면 함수에 이 정보가 반드시 필요하므로 지금 추가해 보겠습니다.
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]
엄청난!행렬의 각 모서리를 성공적으로 회전했습니다.하지만 각 레이어의 중간에 있는 요소는 회전하지 않았습니다.분명히 레이어 내에서 반복하는 방법이 필요합니다.
문제는 지금까지 우리 함수의 유일한 루프(레이어 루프)가 각 반복에서 다음 레이어로 이동한다는 것입니다.행렬에는 회전 가능한 레이어가 하나만 있으므로 모서리만 회전한 후 레이어 루프가 종료됩니다.더 큰 5×5 행렬(두 레이어를 회전해야 하는 경우)에서 어떤 일이 발생하는지 살펴보겠습니다.함수 코드는 생략되었지만 위와 동일하게 유지됩니다.
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 변수와 레이어 내에서 탐색하기 위한 오프셋.우리는 이 새로운 루프를 '요소 루프'라고 부를 것입니다.요소 루프는 맨 위 행의 각 요소, 오른쪽 아래의 각 요소, 맨 아래 행의 각 요소, 왼쪽 위의 각 요소를 방문합니다.
- 상단 행을 따라 앞으로 이동하려면 열 인덱스가 증가해야합니다.
- 오른쪽으로 이동하려면 행 색상이 증가해야합니다.
- 하단을 따라 뒤로 이동하려면 열 인덱스가 줄어들려면됩니다.
- 왼쪽으로 이동하려면 행 색상을 줄여야합니다.
복잡해 보이지만 위의 결과를 얻기 위해 늘리고 줄이는 횟수가 행렬의 네 측면 모두에서 동일하게 유지되기 때문에 쉽습니다.예를 들어:
- 맨 위 행에서 요소 1개를 이동합니다.
- 요소 1개를 오른쪽 아래로 이동합니다.
- 맨 아래 행을 따라 요소 1개를 뒤로 이동합니다.
- 요소 1개를 왼쪽 위로 이동합니다.
이는 단일 변수를 다음과 함께 사용할 수 있음을 의미합니다. first 그리고 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]
이전 게시물에서 말했듯이 다음은 모든 크기의 행렬에 대해 O(1) 행렬 회전을 구현하는 C#의 일부 코드입니다.간결성과 가독성을 위해 오류 검사나 범위 검사가 없습니다.코드:
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) 호출로 대체되었습니다.가상 메소드 호출입니다. ~이다 직접 배열 액세스보다 느리므로 회전 후 회전된 배열이 사용되는 빈도에 따라 달라집니다.한 번만 사용한다면 이 접근 방식이 확실히 승리할 것입니다.회전한 후 며칠 동안 장기 실행 시스템에서 사용하는 경우 내부 회전이 더 나은 성능을 발휘할 수 있습니다.또한 선불 비용을 수용할 수 있는지 여부에 따라 달라집니다.
모든 성능 문제와 마찬가지로 측정, 측정, 측정!
이것은 Java의 더 나은 버전입니다.너비와 높이가 다른 행렬로 만들었습니다.
- 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) 제자리에서 회전을 수행하는 것은 조금 더 까다로울 수 있습니다.약간의 스크래치 공간이 필요합니다(대략 한 행이나 열 크기와 동일).내부 전치 수행에 관한 고대 ACM 문서가 있습니다(http://doi.acm.org/10.1145/355719.355729), 그러나 그들의 예제 코드는 고토가 가득한 FORTRAN입니다.
부록:
http://doi.acm.org/10.1145/355611.355612 또 다른 우수한 것으로 추정되는 내부 전치 알고리즘입니다.
닉의 대답은 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
다음은 Java에 의한 사각형에 대해서만 공간 내 회전 방법입니다.정사각형이 아닌 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 의사코드 구현(예:JavaScript에서 각 행을 바꾼 다음 역순으로 실행합니다.
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
자바 소스 코드 이를 위해:
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
이제 A를 전치하세요.
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
이는 모든 n x n 행렬에 대해 확장 가능합니다.그리고 이 개념을 코드에 빠르게 적용해 보세요.
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]]
구현은 C로 작성된 n^2 전치 함수입니다.여기서 볼 수 있습니다:http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-transpose"전치" 옆에 있는 "소스를 전환하려면 클릭"을 선택하세요.
나는 O(n^2) 솔루션보다 더 잘 기억하지만 특별히 구성된 행렬(예: 희소 행렬)에만 해당됩니다.
M*N 행렬에 대해 시계 방향으로 90도 행렬 회전을 위한 C 코드 IN PLACE
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에서의 In Place 구현이 있습니다.
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:아, 친구.나는 "심심해요. 무엇을 생각할 수 있을까요?"라는 좋은 퍼즐로 이것을 붙잡고 있었습니다.나는 내부 전치 코드를 생각해 냈지만 여기에 와서 당신의 코드가 나와 거의 동일한 것을 발견했습니다...아, 글쎄요.여기는 Ruby입니다.
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++ 방법이지만 큰 배열에서는 큰 메모리 오버헤드가 발생합니다.
