c++ - 将一维向量中表示的矩阵旋转 90 度

Question

我想将矩阵旋转 90 度，以一维向量的形式表示。

当它是 2D 时，这就是我所做的工作：

void rotate(vector<vector<int>>& matrix) {
    reverse(matrix.begin(), matrix.end());
    for (int i = 0; i < matrix.size(); ++i){
        for (int j= i + 1; j < matrix[0].size(); ++j) {
            swap(matrix[i][j], matrix[j][i]);
        }
    }
}

当我以 1D 表示它时，例如：

vector<int> matrix = {1, 2, 3, 4, 5, 6, 7, 8, 9};

这是我尝试过的：

void rotate(vector<int>& matrix, const int& n) {
    int i = 0, j = 0;
    for (i = 0; i < n; ++i) {
        for (j = i + 1; j < n; ++j) {
            swap(matrix[i + j], matrix[i + j * n]);
        }
        reverse(matrix.begin() + i * n, matrix.begin() + (i * n) + j);
    }
}

结果是：

matrix = {7, 4, 1, 6, 5, 8, 9, 2, 3}

但预期的结果应该是：

matrix = {7, 4, 1, 8, 5, 2, 9, 6, 3}

就索引而言，有没有更好的方法来做到这一点或我错过了什么？

标签： c++matrixvector

Answer 1

你几乎明白了。

在这一行：

swap(matrix[i + j], matrix[i + j * n]);

您的第一个索引应该是i * n + j. 这基本上是将 2D 索引转换为 1D 的“公式”（仅适用于方阵）。所以，matrix[i][j]变成matrix[i * n + j]。同样的事情反过来适用：matrix[j][i]变得matrix[j * n + i]，就像你最初在第二个交换参数上所做的那样。

最后，在这一行：

reverse(matrix.begin()+i*n, matrix.begin() + (i*n)+ j);

最后一个表达式应该是(i * n) + n.

为了解释这一点，您可以浏览代码。假设我们到达第二个反向，在内循环完成后，我们处于外循环的第二次迭代（i = 1）。数组在反向之前看起来像这样：

. . . 2 5 8 . . .

我们想将此组反转为：

. . . 8 5 2 . . .

现在为了反转中间部分，我们需要获取这三个数字的索引范围。

在这种情况下，开始索引将是i * n或和（或），其计算结果为，正确表示结束索引。1 * 3 = 3(i * n) + n(i + 1) * n(1 * 3) + 3 = 6