c++ - 在复杂度为 O(1) 的矩阵中切换行和列

Question

因此，对于家庭作业，我的任务之一是使用在类类型对象中构建的矩阵相互交换 2 行或 2 列，使用这 3 个参数来定义它:

size_t _R;// Number of rows.
size_t _C;// Number of columns.
std::vector<T> mat;// array of T type variables to represent the matrix.

例如，如果我有 3 行和 3 列以及 1,2,3,4,5,6,7,8,9 的 int vector 数组，交换第 0 行和第 1 行会使它看起来像 4,5 ,6,1,2,3,7,8,9.

所以让交换发生不是这里的问题，但我不明白的是你打算如何用 O(1) 复杂度来实现交换？
我想做的是在行/列中的每个类型之间单独切换，但那会是 O(n)，对吗？因为它取决于每行/列中的项目数量。

编辑: 我尝试的示例代码:

void swap_rows(const size_t& r1, const size_t& r2) {
    for (size_t i = 0; i < _C; i++)
    {
        T temp = mat[i + (r1 * _C)];
        mat[i + (r1 * _C)] = mat[i + (r2 * _C)];
        mat[i + (r2 * _C)] = temp;
    }
}

但我相信那是 O(n) 复杂度，因此不行 :p

Answer 1

执行此操作的一种方法是对每个维度应用修改行和列，例如:

std::vector<size_t>(_R) row_i;
std::vector<size_t>(_C) col_i;

然后这些都被初始化为例如分别为{0、1、2}。然后，您可以通过这些集合取消引用来访问您的项目:

T getItem( size_t row, size_t column )
{
    return mat[ ( row_i[row] * _C ) + col_i[col] ) ];
}

这将在 row、col 处为您提供项目 T，但通过修改行和列添加取消引用。

现在，例如要交换两行，你只需要说:

std::swap( row_i[0], row_i[1] );

嘿，很快，下次您访问它时，第 0 行和第 1 行将被切换。无论您有 3 x 3 矩阵还是 1000 x 1000 矩阵，修改时间始终只是交换 vector 中的两个整数的时间。