C++程序将矩阵对角线以外的元素沿顺时针方向旋转90度K次

背景

假设有一个 $n\times n$ 的矩阵，现在要将其对角线以外的元素沿顺时针方向旋转90度 $K$ 次，其中 $K$ 是正整数。例如，对于如下的 $3\times 3$ 矩阵：

1   2   3
4   5   6
7   8   9

如果 $K=1$ ，则旋转后的矩阵为：

1   4   7
2   5   8
3   6   9

如果 $K=2$ ，则旋转后的矩阵为：

7   4   1
8   5   2
9   6   3

如果 $K=3$ ，则旋转后的矩阵为：

9   8   7
6   5   4
3   2   1

现在需要实现一个函数rotate_matrix，它接受一个二维数组和旋转的次数，返回旋转后的二维数组。

解法

这是一道比较典型的数组旋转问题，通常的解法是分圈处理。我们可以从外往内一层一层地处理，对于每一层，将其上、右、下、左的元素分别进行交换。例如，在 $k=1$ 的情况下，可以将矩阵的上、右、下、左分别看成如下的一组：

1   2   3              7   4   1
4                   =>  8   5   2
7   8   9              9   6   3

而在 $k=2$ 的情况下，可以再做一次分组，如下所示：

1   2   3              9   8   7              3   2   1
4       6       =>     6   5   4      =>      6   5   4
7   8   9              3   2   1              9   8   7

对于每一层，我们可以用类似于冒泡排序的方法进行交换，假设当前正在处理第 $i$ 层（从外往里数），则需要进行 $n-2i$ 次交换。具体来说，我们可以考虑以下代码实现：

void rotate_layer(vector<vector<int>>& matrix, int k, int layer) {
    int n = matrix.size();
    int start = layer;
    int end = n - layer - 1;

    for (int i = 0; i < k; i++) {
        int temp = matrix[start][start];

        for (int j = start; j < end; j++) {
            matrix[start][j] = matrix[start][j + 1];
        }

        for (int j = start; j < end; j++) {
            matrix[j][end] = matrix[j + 1][end];
        }

        for (int j = end; j > start; j--) {
            matrix[end][j] = matrix[end][j - 1];
        }

        for (int j = end; j > start; j--) {
            matrix[j][start] = matrix[j - 1][start];
        }

        matrix[start + 1][start] = temp;
    }
}

vector<vector<int>> rotate_matrix(vector<vector<int>>& matrix, int k) {
    int n = matrix.size();

    for (int i = 0; i < n / 2; i++) {
        rotate_layer(matrix, k, i);
    }

    return matrix;
}

其中，rotate_layer函数用来旋转一个指定的层，rotate_matrix函数用来对整个矩阵进行旋转。值得注意的是，由于我们对每一层都进行 $k$ 次交换，因此需要在交换的过程中保存每层开头的元素，这个元素需要在最后交换回去，以免被覆盖掉。

测试

我们可以编写一些测试用例来验证函数的正确性，例如：

vector<vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int k = 1;
auto result = rotate_matrix(matrix, k);

// 打印旋转后的矩阵
for (auto row : result) {
    for (auto num : row) {
        cout << num << " ";
    }
    cout << endl;
}

输出：

1 4 7
2 5 8
3 6 9

再试试 $k=2$ 的情况：

vector<vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int k = 2;
auto result = rotate_matrix(matrix, k);

// 打印旋转后的矩阵
for (auto row : result) {
    for (auto num : row) {
        cout << num << " ";
    }
    cout << endl;
}

输出：