如何将二维数组向上旋转？

Question

我正在尝试将一个二维数组的内容向上移动。我有以下的 4*4 二维数组：

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

我想将每一行向上移动，得到以下的数组：

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

这是我的源代码：

#include <iostream>
#include <string>
using namespace std;
const int noCols = 4;

void cycleup(int arr[4][4])
{
    int tmp = 0;

    for (int r2 = 0; r2 < 4; r2++)
    {
        tmp = arr[3][0];
        for (int c = 3; c >= 1; c--)
        {
            arr[c][r2] = arr[c - 1][r2];
        }
        arr[0][r2] = tmp;
    }
}

int main()
{

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

    cycleup(arcg);
    for (int row = 0; row < 4; ++row)
    {
        for (int col = 0; col < 4; ++col)
            cout << "\t" << arcg[row][col];
        cout << endl;
    }
}

然而，我无法获得我想要的输出。你能帮我吗？

- bedirates

---

称之为旋转而非移位。 - user21508463

请描述一下您“无法获得所需的输出”的具体情况。 - user21508463

我的 cycleup() 函数非常简单，就像这样：array2d->i_start = (array2d->i_start + 1) % NUM_ROWS;。看看这里。 这是一种高效的环形缓冲区方法。 - Gabriel Staples

Answer 1

对于许多用例，您可以通过移动索引而不是数据来实现O(1)的等效操作。

• 跟踪row_shift和col_shift，最初都为零。
• 在设置或检索(row, col)的数据时，内部将更新(row, col)为((row + row_shift) % num_rows, (col + col_shift) % num_cols)
• 当移动网格时，改为移动row_shift或col_shift变量。

- Dave

---

点赞。对于那些好奇的人来说，更新索引而不是复制和旋转所有数据效率更高，被称为“环形缓冲区”或“循环缓冲区”。这是一种在嵌入式系统中特别适用的高效FIFO缓冲区常见的架构风格。 - Gabriel Staples

我在我刚刚添加的2D数组环形缓冲区答案中完全展示了这一点。 - Gabriel Staples

Answer 2

基本上看起来你混淆了“行”和“列”。然后你需要给第一行特殊处理。

#include <iostream>
#include <string>
using namespace std;
const int noCols = 4;

void cycleup(int arr[4][4]) {
    int tmp = 0;
    // backup first line
    int first[4];
    for (int c = 0; c < 4; ++c) {
        first[c] = arr[0][c];
    }
    // move up each line but the first
    for (int r2 = 1; r2 < 4; r2++) {
        for (int c = 0; c < 4; ++c) {
            arr[r2 - 1][c] = arr[r2][c];
        }
    }
    // copy backed-up line into the last row
    for (int c = 0; c < 4; ++c) {
        arr[3][c] = first[c];
    }
}

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

    cycleup(arcg);
    for (int row = 0; row < 4; ++row) {
        for (int col = 0; col < 4; ++col) cout << "\t" << arcg[row][col];
        cout << endl;
    }
}

实时演示

- Oersted

---

无需逐行处理，您可以保持操作的顺序。 - user21508463

如果数组很大，按自然顺序迭代可能会提供更好的性能。 - anatolyg

这个可以运作。但是，通过不复制也不移动数组中的任何数据来旋转数组能够提供更好的性能。将数组复制并重写以旋转它的时间复杂度为O(n)，其中n是此情况下行数的数量。我的方法的时间复杂度非常短，无论数组有多大或它有多少行，都为 O(1)。 - Gabriel Staples

Answer 3

您可以使用rotate函数，如下：

int main() {
  using namespace std;
  int arcg[4][4] = { { 3, 7, 6, 5 }, { 5, 8, 2, 4 }, { 9, 7, 3, 1 }, { 8, 2, 1, 0 } };

  std::rotate(arcg[0], arcg[1], arcg[4]);

  for (int row = 0; row < 4; ++row) {
    for (int col = 0; col < 4; ++col)
      cout << "\t" << arcg[row][col];
    cout << endl;
  }
}

这是一个将第二和第三行移动到末尾的示例：

  std::array<std::array<int, 4>, 4> a { { { 3, 7, 6, 5 }, { 5, 8, 2, 4 }, { 9, 7, 3, 1 }, { 8, 2, 1, 0 } } };

  auto first_row       = 1;
  auto last_row        = 2;
  auto destination_row = 3;

  auto f   = a.begin() + first_row;
  auto f_n = a.begin() + last_row + 1;
  auto l   = a.begin() + destination_row + 1;

  std::rotate(f, f_n, l);

- Tassos

Answer 4

伪代码：

• 对于每一列
  • 保存顶部元素
  • 对于除第一行之外的每一行
    • 向上复制元素 (row, column)
  • 将保存的元素复制到底部行

- user21508463

Answer 5

通过将二维数组视为“环形缓冲区”或“循环缓冲区”高效地向上旋转

不要复制或移动二维数组中的数据。这样不高效。相反，我们可以通过移动一个i_start行索引来旋转这个二维数组，将整个数组视为{{link1：“环形缓冲区”或“循环缓冲区”}}，这是一种常见的架构风格，特别适用于嵌入式系统中的高效FIFO缓冲区。

@Dave在此处的答案中提到了这个概念。

将数组复制和/或重写以旋转它的时间复杂度等于O(n)，其中n是此情况下行数的数量。我下面的方法的时间复杂度非常短，为O(1)，无论数组有多大或有多少行，因为我们所做的只是将其“旋转”上去：array2d->i_start = (array2d->i_start + 1) % NUM_ROWS;，这是非常高效的！

这是使用C++中的C语言风格数组对此概念的完整演示。请注意，如果您仅仅去掉下面结构体中的=0;部分并且还 typedef 它（我个人偏好）或者 在需要的地方添加struct单词，这也将成为一个完全有效的C程序。

来自我的eRCaGuy_hello_world 仓库的 cpp/ring_buffer_rotate_2d_array_up.cpp:

///usr/bin/env ccache g++ -Wall -Wextra -Werror -O3 -std=gnu++17 "$0" -o /tmp/a && /tmp/a "$@"; exit
// For the line just above, see my answer here: https://dev59.com/r3E95IYBdhLWcg3wDpcG#75491834

// C++ (incl. C) includes
#include <cstdio>   // For `printf()`
#include <iostream>  // For `std::cin`, `std::cout`, `std::endl`, etc.

// Get the number of elements in any C array
// - from my repo here:
//   https://github.com/ElectricRCAircraftGuy/eRCaGuy_hello_world/blob/master/c/utilities.h#L42
#define ARRAY_LEN(array) (sizeof(array) / sizeof((array)[0]))

/// Definitions: `rows` = "rows"; `cols` = "columns"

/// Get number of rows in a 2D array
#define NUM_ROWS(array_2d) ARRAY_LEN(array_2d)
/// Get number of columns in a 2D array
#define NUM_COLS(array_2d) ARRAY_LEN((array_2d)[0])


struct Array2d
{
    // the actual C-style 2D array of data
    int array[4][4];
    // the starting index for the array, which represents the "first row"
    size_t i_start = 0;
};

// Print the 2D array.
// - Note: pass by const reference since we won't change the array while
//   printing.
void array2d_print(const Array2d& array2d)
{
    const size_t NUM_ROWS = NUM_ROWS(array2d.array);
    const size_t NUM_COLS = NUM_COLS(array2d.array);

    size_t i_row = array2d.i_start;
    for (size_t row = 0; row < NUM_ROWS; row++)
    {
        for (size_t i_col = 0; i_col < NUM_COLS; i_col++)
        {
            printf("%3i", (array2d.array)[i_row][i_col]);
            if (i_col < NUM_COLS - 1)
            {
                printf(",");
            }
            else
            {
                printf("\n");
            }
        }

        // increment our "ring-buffer-style" row index
        i_row = (i_row + 1) % NUM_ROWS;
    }
    printf("\n");
}

// Rotate the 2D array up.
// - Note: pass by ptr since we **will** change the array (the `i_start` index
//   in this case), and we want this fact to be obvious when the user calls
//   this function.
void array2d_rotateup(Array2d* array2d)
{
    const size_t NUM_ROWS = NUM_ROWS(array2d->array);
    // Note: since the `i_start` index is an **unsigned** integer `size_t` type,
    // this approach works perfectly fine even if the integer value overflows
    // upward and rolls over, so there is never a need to check for overflow.
    // This works fine and is well-defined behavior as-is. **Signed** integers,
    // however, have technically **undefined** behavior during overflow and
    // underflow.
    array2d->i_start = (array2d->i_start + 1) % NUM_ROWS;
}

int main()
{
    Array2d array2d =
    {
        .array =
        {
            {1,   2,  3,  4},
            {5,   6,  7,  8},
            {9,  10, 11, 12},
            {13, 14, 15, 16},
        }
    };

    // print the starting array
    array2d_print(array2d);

    // now rotate and print the array NUM_ROWS times
    for (size_t i = 0; i < NUM_ROWS(array2d.array); i++)
    {
        array2d_rotateup(&array2d);
        array2d_print(array2d);
    }

    return 0;
}

运行命令和输出：

eRCaGuy_hello_world$ cpp/ring_buffer_rotate_2d_array_up.cpp
  1,  2,  3,  4
  5,  6,  7,  8
  9, 10, 11, 12
 13, 14, 15, 16

  5,  6,  7,  8
  9, 10, 11, 12
 13, 14, 15, 16
  1,  2,  3,  4

  9, 10, 11, 12
 13, 14, 15, 16
  1,  2,  3,  4
  5,  6,  7,  8

 13, 14, 15, 16
  1,  2,  3,  4
  5,  6,  7,  8
  9, 10, 11, 12

  1,  2,  3,  4
  5,  6,  7,  8
  9, 10, 11, 12
 13, 14, 15, 16

参考文献

1. [我的关于二维数组的回答] 如何在C和C ++中将多维数组（例如2D数组）及其指针作为函数参数使用

另请参阅

1. 有关环形缓冲区的更多信息，包括完整的演示/库模块，请查看我在eRCaGuy_hello_world存储库中的containers_ring_buffer_FIFO.c文件。

- Gabriel Staples