旋转二维数组的最快方法

Question

我正在寻找在2D数组/矩阵中旋转行的最佳算法。假设我们有

mat[3][3] = {{1,2,3},{4,5,6},{7,8,9}};

我想将元素向左移动一位，那么第一行的1 2 3就会变成2 3 1。该函数通过动态内存分配将每个元素复制到左侧来实现这一点。

void rotate_row(const int& row) {

    int *temp_row = (int *) (malloc(3));
    for (int i = 0; i < 3; ++i) {
        temp_row[i % 3] = mat[row][(i + 1) % 3];

    }

    memcpy(mat[row], temp_row, 3);
    free(temp_row);
}

要操作任何特定的行，我们只需调用函数rotate_row(row)。

我不太理解C中的malloc东西，因为我从小学习了一种全新的动态分配方法，所以我先把它改成：

void rotate_rows(const int& row) {
    //int *temp_row = (int *) (malloc(3));
    int *temp_row = new int[3];
    for (int i = 0; i < 3; ++i) {
        temp_row[i % 3] = mat[row][(i + 1) % 3];

    }
    memcpy( mat[row], temp_row, 3);
    //free(temp_row);
    delete [] temp_row;
    temp_row = NULL;
}

我的问题首先是，简单地改变动态内存分配的方式会加速代码吗？

此外，我认为没有必要使用动态内存分配来达到我的目的(旋转行)。他们有没有更好的(不一定是最好的)算法？

Answer 1

旋转不会改变数组的大小，因此原地操作对我来说听起来性能更好，不需要动态内存分配和释放前一个指针。

void rotate(int * array, size_t n) {
    if (n <= 1)
        return;

    const int head = array[0];

    for (size_t i = 1; i < n; ++i)
        array[i - 1] = array[i];
    array[n - 1] = head;
}

Answer 2

您可以避免所有的动态内存分配，并使用std::rotate算法：

#include <algorithm>
#include <iostream>

int main()
{
    int mat[3][3] = { {1,2,3},{4,5,6},{7,8,9} };

    // rotate left each row by 1
    for (int i = 0; i < 3; ++i)
        std::rotate(&mat[i][0], &mat[i][1], &mat[i][3]);

    for (int i = 0; i < 3; ++i)
        std::cout << mat[i][0] << " " << mat[i][1] << " " << mat[i][2] << "\n";
}

输出：

2 3 1
5 6 4
8 9 7

编辑：

下面是按照每行的行索引加1来旋转每一行的示例：

#include <algorithm>
#include <iostream>

int main()
{
    int mat[3][3] = { {1,2,3},{4,5,6},{7,8,9} };

    // rotate left each row by 1
    for (int i = 0; i < 3; ++i)
        std::rotate(&mat[i][0], &mat[i][i+1], &mat[i][3]);

    for (int i = 0; i < 3; ++i)
        std::cout << mat[i][0] << " " << mat[i][1] << " " << mat[i][2] << "\n";
}

输出：

2 3 1
6 4 5
7 8 9

Answer 3

是的，有一种更好的方法，不需要使用动态内存分配。你实际上不需要另一个数组来解决这个问题。下面是一个示例代码：

    for(int i = 0; i < n/2; i++){
        for(int j = i; j < n-i-1; j++){
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[n-j-1][i];
            matrix[n-j-1][i] = matrix[n-i-1][n-j-1];
            matrix[n-i-1][n-j-1] = matrix[j][n-i-1];
            matrix[j][n-i-1] = tmp;
        }
    }

这是非常直接的，所以我认为你不需要解释就可以很容易地理解代码。