受Raymond Chen帖子的启发，假设你有一个4x4二维数组，写一个函数使它旋转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²更好的方法呢?如果矩阵是10000x10000呢?
当前回答
这是一个如今被高估的面试问题。
我的建议是:不要让面试官用他们关于解决这个问题的疯狂建议把你弄糊涂了。使用白板绘制输入数组的索引，然后绘制输出数组的索引。旋转前后的列分度示例如下:
30 --> 00
20 --> 01
10 --> 02
00 --> 03
31 --> 10
21 --> 11
11 --> 12
01 --> 13
注意旋转后的数字模式。
下面提供了一个简洁的Java解决方案。经过测试，它是有效的:
Input:
M A C P
B N L D
Y E T S
I W R Z
Output:
I Y B M
W E N A
R T L C
Z S D P
/**
* (c) @author "G A N MOHIM"
* Oct 3, 2015
* RotateArrayNintyDegree.java
*/
package rotatearray;
public class RotateArrayNintyDegree {
public char[][] rotateArrayNinetyDegree(char[][] input) {
int k; // k is used to generate index for output array
char[][] output = new char[input.length] [input[0].length];
for (int i = 0; i < input.length; i++) {
k = 0;
for (int j = input.length-1; j >= 0; j--) {
output[i][k] = input[j][i]; // note how i is used as column index, and j as row
k++;
}
}
return output;
}
public void printArray(char[][] charArray) {
for (int i = 0; i < charArray.length; i++) {
for (int j = 0; j < charArray[0].length; j++) {
System.out.print(charArray[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
char[][] input =
{ {'M', 'A', 'C', 'P'},
{'B', 'N', 'L', 'D'},
{'Y', 'E', 'T', 'S'},
{'I', 'W', 'R', 'Z'}
};
char[][] output = new char[input.length] [input[0].length];
RotateArrayNintyDegree rotationObj = new RotateArrayNintyDegree();
rotationObj.printArray(input);
System.out.println("\n");
output = rotationObj.rotateArrayNinetyDegree(input);
rotationObj.printArray(output);
}
}
其他回答
这是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;
}
为新手程序员，在纯c++。(宝蓝的东西)
#include<iostream.h>
#include<conio.h>
int main()
{
clrscr();
int arr[10][10]; // 2d array that holds input elements
int result[10][10]; //holds result
int m,n; //rows and columns of arr[][]
int x,y; //rows and columns of result[][]
int i,j; //loop variables
int t; //temporary , holds data while conversion
cout<<"Enter no. of rows and columns of array: ";
cin>>m>>n;
cout<<"\nEnter elements of array: \n\n";
for(i = 0; i < m; i++)
{
for(j = 0; j<n ; j++)
{
cin>>arr[i][j]; // input array elements from user
}
}
//rotating matrix by +90 degrees
x = n ; //for non-square matrix
y = m ;
for(i = 0; i < x; i++)
{ t = m-1; // to create required array bounds
for(j = 0; j < y; j++)
{
result[i][j] = arr[t][i];
t--;
}
}
//print result
cout<<"\nRotated matrix is: \n\n";
for(i = 0; i < x; i++)
{
for(j = 0; j < y; j++)
{
cout<<result[i][j]<<" ";
}
cout<<"\n";
}
getch();
return 0;
}
这是我的实现，在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;
}
}
}
c#代码将[n,m] 2D数组向右旋转90度
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
我想再补充一点细节。在这个答案中，关键概念被重复，节奏缓慢，故意重复。这里提供的解决方案在语法上不是最紧凑的，但是，它是为那些希望了解什么是矩阵旋转及其实现的人设计的。
首先，什么是矩阵?为了回答这个问题，矩阵就是一个宽度和高度相同的网格。注意，矩阵的宽度和高度可以不同，但是为了简单起见，本教程只考虑宽度和高度相等的矩阵(方阵)。是的，矩阵是矩阵的复数形式。
例如:2×2, 3×3或5×5。或者更通俗地说，N×N。2×2矩阵将有4个方框，因为2×2=4。一个5×5矩阵将有25个正方形，因为5×5=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.
矩阵将使用一个二维数组定义:
matrix = [
[0,1],
[2,3]
]
因此，第一个索引位置访问行。第二个索引位置访问列:
matrix[row][column]
我们将定义一个效用函数来打印一个矩阵。
def print_matrix(matrix):
for row in matrix:
print row
旋转矩阵的一种方法是一次旋转一层。但是什么是层呢?想象一个洋葱。就像洋葱的一层一层，随着每一层的移除，我们向中心移动。另一个类比是俄罗斯套娃或传递包裹的游戏。
矩阵的宽度和高度决定了该矩阵的层数。让我们为每一层使用不同的符号:
2×2矩阵有1层
. .
. .
3×3矩阵有两层
. . .
. x .
. . .
4×4矩阵有两层
. . . .
. 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 .
. . . . . . .
你可能会注意到，矩阵的宽度和高度增加一，并不总是增加层数。以上述矩阵为例，将层数和维度制成表格，我们可以看到层数每增加两个宽度和高度就会增加一次:
+-----+--------+
| 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矩阵)形成时，就会发生这种情况，因此不需要旋转。它只是被忽略了。
毫无疑问，我们在函数中需要这个信息来旋转一个矩阵，所以让我们现在添加它:
def rotate(matrix):
size = len(matrix)
# Rotatable layers only.
layer_count = size / 2
现在我们知道什么是层，以及如何确定实际需要旋转的层数，我们如何隔离单个层以便我们可以旋转它?首先，我们检查一个矩阵，从最外层，向内，到最内层。5×5矩阵总共有三层，其中两层需要旋转:
. . . . .
. 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 | . . . . . |
+-----+-----------+
这将总是这样，因为宽度和高度是相同的。因此，我们可以用两个值(而不是四个)定义一个层的列和行位置。
向内移动到第二层，列的位置为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
现在我们有了一个循环，提供了每一层的行和列的位置。变量第一个和最后一个标识第一个和最后一个行和列的索引位置。回到行表和列表:
+--------+-----------+
| 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 |
+-----+-------+
因为我们的矩阵总是方阵，我们只需要两个变量，第一个和最后一个，因为行和列的下标位置是相同的。
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.
第一个和最后一个变量可以很容易地用于引用矩阵的四个角。这是因为角本身可以使用第一个和最后一个的各种排列来定义(不需要对这些变量进行减法、加法或偏移):
+---------------+-------------------+-------------+
| 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 *
我们要把每个*和它右边的*交换。所以让我们继续打印我们的角，只使用第一和最后的不同排列来定义:
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]
It shouldn’t be a surprise that the corners of the outermost layer have been rotated, but, you may also notice the corners of the next layer (inwards) have also been rotated. This makes sense. We’ve written code to navigate through layers and also to rotate the corners of each layer. This feels like progress, but unfortunately we must take a step back. It’s just no good moving onto the next layer until the previous (outer) layer has been fully rotated. That is, until each element in the layer has been rotated. Rotating only the corners won’t do!
深呼吸。我们需要另一个循环。一个嵌套循环。新的嵌套循环将使用第一个和最后一个变量，加上一个偏移量来在层内导航。我们将这个新循环称为“element loop”。元素循环将访问顶部一行的每个元素、右侧一行的每个元素、底部一行的每个元素和左侧一行的每个元素。
沿着顶部行向前移动需要列 要递增的索引。 向右移动要求行索引为 递增。 沿着底部向后移动需要列 要递减的索引。 向左侧移动要求行索引为 递减。
这听起来很复杂，但它很简单，因为我们为实现上述目标所增加和减少的次数在矩阵的四个边都是相同的。例如:
移动第一行的一个元素。 向右移动一个元素。 沿着最下面一行向后移动一个元素。 把一个元素移到左边。
这意味着我们可以将单个变量与第一个和最后一个变量结合使用来在一个层中移动。注意从上一行移动到右一行都需要递增，这可能会有所帮助。当沿着底部和左侧向上向后移动时，两者都需要递减。
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 = (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
旋转函数的结果是:
6, 3, 0
7, 4, 1
8, 5, 2
推荐文章
- 圆线段碰撞检测算法?
- 求有向图中的所有循环
- JavaScript -从当前日期开始获取一周的第一天
- 如何比较两种颜色的相似/不同
- 有效的方法应用多个过滤器的熊猫数据框架或系列
- 哪些是遗传算法/遗传规划解决方案的好例子?
- 在JavaScript中调换2d数组
- 如何在O(n)中找到长度为n的无序数组中的第k大元素?
- 一个用于膨胀/收缩(抵消，缓冲)多边形的算法
- 我如何使用Node.js Crypto创建HMAC-SHA1哈希?
- 如何用动态规划确定最长递增子序列?
- 在c++程序中以编程方式检测字节序
- 理解递归
- 段树、区间树、二叉索引树和范围树之间有什么区别?
- 给定一个数字，找出下一个与原始数字具有完全相同的数字集的更高的数字
