Как вы вращаете двумерный массив?

Question

Вдохновленный Пост Раймонда Чена , скажем, у вас есть двумерный массив 4x4, напишите функцию, которая поворачивает его на 90 градусов. Раймонд ссылается на решение в псевдокоде, но я хотел бы увидеть некоторые реальные вещи.

[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]

Обновление : ответ Ника самый простой, но есть ли способ сделать это лучше, чем n ^ 2? Что, если матрица была 10000x10000?

Answer 1

Может быть сделано рекурсивно довольно чисто, вот моя реализация в golang!

рекурсивно вращать матрицу nxn в go golang без дополнительной памяти

func rot90(a [][]int) {
    n := len(a)
    if n == 1 {
        return
    }
    for i := 0; i < n; i++ {
        a[0][i], a[n-1-i][n-1] = a[n-1-i][n-1], a[0][i]
    }
    rot90(a[1:])
}

Answer 2

Это вопрос переоценки в наши дни.

Мое предложение таково: не позволяйте интервьюеру путать вас с его сумасшедшим предложением о решении этой проблемы. Используйте доску, чтобы нарисовать индексирование входного массива, затем нарисуйте индексирование выходного массива. Образцы индексации столбцов до и после вращения показаны ниже:

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);

    }

}

Answer 3

Вот решение 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

Answer 4

Алгоритм памяти O (1):

1. поверните самые внешние данные, тогда вы можете получить результат ниже:

   [3][9][5][1]
   [4][6][7][2]
   [5][0][1][3]
   [6][2][8][4]
   

Чтобы сделать это вращение, мы знаем

    dest[j][n-1-i] = src[i][j]

Соблюдайте ниже: а (0,0) -> а (0,3) а (0,3) -> а (3,3) а (3,3) -> а (3,0) а (3,0) -> а (0,0)

Следовательно, это круг, вы можете вращать N элементов за один цикл. Сделайте эту петлю N-1, чтобы повернуть самые внешние элементы.

1. Теперь вы можете внутренний вопрос тот же вопрос для 2X2.

Поэтому мы можем сделать вывод, как показано ниже:

function rotate(array, N)
{
    Rotate outer-most data
    rotate a new array with N-2 or you can do the similar action following step1
}

Answer 5

#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];

       }
}

Answer 6

Моя версия ротации:

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];
}

В нем мы меняем последний столбец на первый ряд и так далее. Это может быть не оптимально, но понятно для понимания.

Answer 7

Основываясь на множестве других ответов, я придумал это в C #:

/// <param name="rotation">The number of rotations (if negative, the <see cref="Matrix{TValue}"/> is rotated counterclockwise; 
/// otherwise, it's rotated clockwise). A single (positive) rotation is equivalent to 90° or -270°; a single (negative) rotation is 
/// equivalent to -90° or 270°. Matrices may be rotated by 90°, 180°, or 270° only (or multiples thereof).</param>
/// <returns></returns>
public Matrix<TValue> Rotate(int rotation)
{
    var result = default(Matrix<TValue>);

    //This normalizes the requested rotation (for instance, if 10 is specified, the rotation is actually just +-2 or +-180°, but all 
    //correspond to the same rotation).
    var d = rotation.ToDouble() / 4d;
    d = d - (int)d;

    var degree = (d - 1d) * 4d;

    //This gets the type of rotation to make; there are a total of four unique rotations possible (0°, 90°, 180°, and 270°).
    //Each correspond to 0, 1, 2, and 3, respectively (or 0, -1, -2, and -3, if in the other direction). Since
    //1 is equivalent to -3 and so forth, we combine both cases into one. 
    switch (degree)
    {
        case -3:
        case +1:
            degree = 3;
            break;
        case -2:
        case +2:
            degree = 2;
            break;
        case -1:
        case +3:
            degree = 1;
            break;
        case -4:
        case  0:
        case +4:
            degree = 0;
            break;
    }
    switch (degree)
    {
        //The rotation is 0, +-180°
        case 0:
        case 2:
            result = new TValue[Rows, Columns];
            break;
        //The rotation is +-90°
        case 1:
        case 3:
            result = new TValue[Columns, Rows];
            break;
    }

    for (uint i = 0; i < Columns; ++i)
    {
        for (uint j = 0; j < Rows; ++j)
        {
            switch (degree)
            {
                //If rotation is 0°
                case 0:
                    result._values[j][i] = _values[j][i];
                    break;
                //If rotation is -90°
                case 1:
                    //Transpose, then reverse each column OR reverse each row, then transpose
                    result._values[i][j] = _values[j][Columns - i - 1];
                    break;
                //If rotation is +-180°
                case 2:
                    //Reverse each column, then reverse each row
                    result._values[(Rows - 1) - j][(Columns - 1) - i] = _values[j][i];
                    break;
                //If rotation is +90°
                case 3:
                    //Transpose, then reverse each row
                    result._values[i][j] = _values[Rows - j - 1][i];
                    break;
            }
        }
    }
    return result;
}

Где _values соответствует частному двумерному массиву, определенному Matrix<TValue> (в форме [][]). result = new TValue[Columns, Rows] возможно через неявную перегрузку оператора и преобразует двумерный массив в Matrix<TValue>. Два свойства Columns и Rows являются открытыми свойствами, которые получают количество столбцов и строк текущего экземпляра:

public uint Columns 
    => (uint)_values[0].Length;

public uint Rows 
    => (uint)_values.Length;

Предполагая, конечно, что вы предпочитаете работать с беззнаковыми индексами; -)

Все это позволяет вам указать, сколько раз его следует повернуть и нужно ли поворачивать влево (если меньше нуля) или вправо (если больше нуля). Вы можете улучшить это, чтобы проверять вращение в фактических градусах, но затем вы захотите вызвать исключение, если значение не кратно 90. С этим входом вы можете изменить метод соответствующим образом:

public Matrix<TValue> Rotate(int rotation)
{
    var _rotation = (double)rotation / 90d;

    if (_rotation - Math.Floor(_rotation) > 0)
    {
        throw new NotSupportedException("A matrix may only be rotated by multiples of 90.").
    }

    rotation = (int)_rotation;
    ...
}

Поскольку степень более точно выражена double, чем int, но матрица может вращаться только с кратным 90, гораздо более интуитивно понятно, чтобы аргумент соответствовал чему-то еще, что может быть точно представлено структура данных используется. int идеально, потому что он может сказать вам, сколько раз повернуть его до определенной единицы (90), а также направление. double вполне может также рассказать вам об этом, но также включает в себя значения, которые не поддерживаются этой операцией (что по своей сути нелогично).

Answer 8

Все текущие решения имеют O (n ^ 2) в качестве служебного пространства (это исключает эти грязные OOP-читеры!). Вот решение с использованием 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]);
}

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: На самом деле я не проверял это. Давайте поиграем в баг-баг!

Answer 9

Это решение не заботится о квадрате или прямоугольнике, вы можете вращать 4x5 или 5x4 или даже 4x4, ему также не нужен размер. Обратите внимание, что эта реализация создает новый массив каждый раз, когда вы вызываете метод rotate90, она вообще не изменяет исходный массив.

public static void main(String[] args) {
    int[][] a = new int[][] { 
                    { 1, 2, 3, 4 }, 
                    { 5, 6, 7, 8 }, 
                    { 9, 0, 1, 2 }, 
                    { 3, 4, 5, 6 }, 
                    { 7, 8, 9, 0 } 
                  };
    int[][] rotate180 = rotate90(rotate90(a));
    print(rotate180);
}

static int[][] rotate90(int[][] a) {
    int[][] ret = new int[a[0].length][a.length];
    for (int i = 0; i < a.length; i++) {
        for (int j = 0; j < a[i].length; j++) {
            ret[j][a.length - i - 1] = a[i][j];
        }
    }
    return ret;
}

static void print(int[][] array) {
    for (int i = 0; i < array.length; i++) {
        System.out.print("[");
        for (int j = 0; j < array[i].length; j++) {
            System.out.print(array[i][j]);
            System.out.print(" ");
        }
        System.out.println("]");
    }
}

Answer 10

Вот рекурсивный способ 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>';