受雷蒙德·陈的帖子的启发，假设你有一个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^2更好的方法呢？如果矩阵是10000x10000呢？
如何旋转一个二维数组？
359
- swilliams
13
114你怎么可能只用少于n^2的步骤？所有元素都必须读取和设置，而且有n^2个元素。 - erikkallen
9您的n是多少？您没有说明2D数组是否为正方形（一般情况下并非如此！例如，向量是具有一个维度为1的矩阵），但是您似乎在暗示n是宽度和高度，并且因此有n²个元素。更合理的做法是让n成为元素数量，其中n=w×h。 - niXar
1以下是一种快速的方法：存储行和列索引（例如 i 和 j）。转置只需要常数时间（只需交换索引即可 :)）。您可以使用旋转进行相同的操作（玩转索引）。 - mrk
4如果n^2不可行，您可以创建一个接口来访问每个元素。然后，给定(i,j)，对(i,j)应用旋转操作以访问旋转后的元素并返回其值。这可能不是最佳解决方案，但是可以使用。 - Confuse
1我认为你仍然可以在小于N^2的时间内完成它。但是，需要使用更复杂的数据结构。也许是某种双向链表？ - Younes Nj
显示剩余8条评论
64个回答
0
这里是一个递归的 PHP 方法：
$m = array();
$m[0] = array('a', 'b', 'c');
$m[1] = array('d', 'e', 'f');
$m[2] = array('g', 'h', 'i');
$newMatrix = array();
function rotateMatrix($m, $i = 0, &$newMatrix)
{
foreach ($m as $chunk) {
$newChunk[] = $chunk[$i];
}
$newMatrix[] = array_reverse($newChunk);
$i++;
if ($i < count($m)) {
rotateMatrix($m, $i, $newMatrix);
}
}
rotateMatrix($m, 0, $newMatrix);
echo '<pre>';
var_dump($newMatrix);
echo '<pre>';
- taxicala
0
我的旋转版本：
void rotate_matrix(int *matrix, int size)
{
int result[size*size];
for (int i = 0; i < size; ++i)
for (int j = 0; j < size; ++j)
result[(size - 1 - i) + j*size] = matrix[i*size+j];
for (int i = 0; i < size*size; ++i)
matrix[i] = result[i];
}
在这里，我们将最后一列变为第一行，依此类推。这可能不是最优解，但对于理解来说很清晰。
- Alex
0
目前的所有解决方案都具有 O(n^2) 的额外空间开销（不包括那些肮脏的面向对象编程作弊者！）。这里提供了一种使用 O(1) 内存的解决方案，可以原地将矩阵顺时针旋转 90 度。忽略可扩展性，这家伙运行速度很快！
#include <algorithm>
#include <cstddef>
// Rotates an NxN matrix of type T 90 degrees to the right.
template <typename T, size_t N>
void rotate_matrix(T (&matrix)[N][N])
{
for(size_t i = 0; i < N; ++i)
for(size_t j = 0; j <= (N-i); ++j)
std::swap(matrix[i][j], matrix[j][i]);
}
声明：我并没有真正测试过这个。让我们来玩打虫子游戏吧！
- Clark Gaebel
1
5这不仅转置了矩阵，而没有旋转它吗？ - recursive
0
#include <iostream>
#include <iomanip>
using namespace std;
const int SIZE=3;
void print(int a[][SIZE],int);
void rotate(int a[][SIZE],int);
void main()
{
int a[SIZE][SIZE]={{11,22,33},{44,55,66},{77,88,99}};
cout<<"the array befor rotate\n";
print(a,SIZE);
rotate( a,SIZE);
cout<<"the array after rotate\n";
print(a,SIZE);
cout<<endl;
}
void print(int a[][SIZE],int SIZE)
{
int i,j;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
cout<<a[i][j]<<setw(4);
}
void rotate(int a[][SIZE],int SIZE)
{
int temp[3][3],i,j;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE/2.5;j++)
{
temp[i][j]= a[i][j];
a[i][j]= a[j][SIZE-i-1] ;
a[j][SIZE-i-1] =temp[i][j];
}
}
- loOoly
0
我能够用一个循环完成这个任务。时间复杂度看起来像是O(K)，其中K是数组中的所有项目。
以下是我在JavaScript中实现它的方法：
首先，我们用单个数组表示n^2矩阵。然后，像这样遍历它：
/**
* Rotates matrix 90 degrees clockwise
* @param arr: the source array
* @param n: the array side (array is square n^2)
*/
function rotate (arr, n) {
var rotated = [], indexes = []
for (var i = 0; i < arr.length; i++) {
if (i < n)
indexes[i] = i * n + (n - 1)
else
indexes[i] = indexes[i - n] - 1
rotated[indexes[i]] = arr[i]
}
return rotated
}
基本上，我们会转换源数组的索引：
[0,1,2,3,4,5,6,7,8] => [2,5,8,1,4,7,0,3,6]
然后，使用这个经过转换的 indexes 数组，在最终的 rotated 数组中放置实际值。
以下是一些测试用例：
//n=3
rotate([
1, 2, 3,
4, 5, 6,
7, 8, 9], 3))
//result:
[7, 4, 1,
8, 5, 2,
9, 6, 3]
//n=4
rotate([
1, 2, 3, 4,
5, 6, 7, 8,
9, 10, 11, 12,
13, 14, 15, 16], 4))
//result:
[13, 9, 5, 1,
14, 10, 6, 2,
15, 11, 7, 3,
16, 12, 8, 4]
//n=5
rotate([
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], 5))
//result:
[21, 16, 11, 6, 1,
22, 17, 12, 7, 2,
23, 18, 13, 8, 3,
24, 19, 14, 9, 4,
25, 20, 15, 10, 5]
- advncd
2
1这在技术上仍然是 n^2，因为 k = n^2。但是这是个好主意啊，而且我相当确信 n^2 是旋转 2D 数组的最小时间复杂度。 - Yolomep
这是一个无用的答案。OP有一个二维数组，但你假设该数组是作为单个数组而不是二维数组或数组的数组给出的。即使你想从二维数组创建一个单一数组，你也必须读取每个元素，这将导致n^2的时间复杂度。 - YaMiN
0
在 Eigen（C++）中：
Eigen::Matrix2d mat;
mat << 1, 2,
3, 4;
std::cout << mat << "\n\n";
Eigen::Matrix2d r_plus_90 = mat.transpose().rowwise().reverse();
std::cout << r_plus_90 << "\n\n";
Eigen::Matrix2d r_minus_90 = mat.transpose().colwise().reverse();
std::cout << r_minus_90 << "\n\n";
Eigen::Matrix2d r_180 = mat.colwise().reverse().rowwise().reverse(); // +180 same as -180
std::cout << r_180 << "\n\n";
输出：
1 2
3 4
3 1
4 2
2 4
1 3
4 3
2 1
- Meow
0
这是一个JavaScript的解决方案：
const transpose = m => m[0].map((x,i) => m.map(x => x[i]));
a: // original matrix
123
456
789
transpose(a).reverse(); // rotate 90 degrees counter clockwise
369
258
147
transpose(a.slice().reverse()); // rotate 90 degrees clockwise
741
852
963
transpose(transpose(a.slice().reverse()).slice().reverse())
// rotate 180 degrees
987
654
321
- user1663023
-1
这是我为@dimple所提供的伟大算法编写的C#示例代码：
/* Author: Dudi,
* http://www.tutorialspoint.com/compile_csharp_online.php?PID=0Bw_CjBb95KQMYm5qU3VjVGNuZFU */
using System.IO;
using System;
class Program
{
static void Main()
{
Console.WriteLine("Rotating this matrix by 90+ degree:");
int[,] values=new int[3,3]{{1,2,3}, {4,5,6}, {7,8,9}};
//int[,] values=new int[4,4]{{101,102,103, 104}, {105,106, 107,108}, {109, 110, 111, 112}, {113, 114, 115, 116}};
print2dArray(ref values);
transpose2dArray(ref values);
//print2dArray(ref values);
reverse2dArray(ref values);
Console.WriteLine("Output:");
print2dArray(ref values);
}
static void print2dArray(ref int[,] matrix){
int nLen = matrix.GetLength(0);
int mLen = matrix.GetLength(1);
for(int n=0; n<nLen; n++){
for(int m=0; m<mLen; m++){
Console.Write(matrix[n,m] +"\t");
}
Console.WriteLine();
}
Console.WriteLine();
}
static void transpose2dArray(ref int[,] matrix){
int nLen = matrix.GetLength(0);
int mLen = matrix.GetLength(1);
for(int n=0; n<nLen; n++){
for(int m=0; m<mLen; m++){
if(n>m){
int tmp = matrix[n,m];
matrix[n,m] = matrix[m,n];
matrix[m,n] = tmp;
}
}
}
}
static void reverse2dArray(ref int[,] matrix){
int nLen = matrix.GetLength(0);
int mLen = matrix.GetLength(1);
for(int n=0; n<nLen; n++){
for(int m=0; m<mLen/2; m++){
int tmp = matrix[n,m];
matrix[n,m] = matrix[n, mLen-1-m];
matrix[n,mLen-1-m] = tmp;
}
}
}
}
/*
Rotating this matrix by 90+ degree:
1 2 3
4 5 6
7 8 9
Output:
7 4 1
8 5 2
9 6 3
*/
- Dudi
2
我没听懂你说什么？ - Dudi
（比较版本。不会涉及空格、逗号、运算符或不使用“swap”原语。） - greybeard
-1
/* 90-degree clockwise:
temp_array = left_col
left_col = bottom_row
bottom_row = reverse(right_col)
reverse(right_col) = reverse(top_row)
reverse(top_row) = temp_array
*/
void RotateClockwise90(int ** arr, int lo, int hi) {
if (lo >= hi)
return;
for (int i=lo; i<hi; i++) {
int j = lo+hi-i;
int temp = arr[i][lo];
arr[i][lo] = arr[hi][i];
arr[hi][i] = arr[j][hi];
arr[j][hi] = arr[lo][j];
arr[lo][j] = temp;
}
RotateClockwise90(arr, lo+1, hi-1);
}
- Shiva
-1
JavaScript中旋转矩阵90度的解决方案：
function rotateBy90(m) {
var length = m.length;
//for each layer of the matrix
for (var first = 0; first < length >> 1; first++) {
var last = length - 1 - first;
for (var i = first; i < last; i++) {
var top = m[first][i]; //store top
m[first][i] = m[last - i][first]; //top = left
m[last - i][first] = m[last][last - i]; //left = bottom
m[last][last - i] = m[i][last]; //bottom = right
m[i][last] = top; //right = top
}
}
return m;
}
- spark
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接