交换向量表示的矩阵中的两列

Question

我遇到以下问题：我有一个表示二维矩阵的向量，我有行数和列数以及其他一些不相关的东西。

// A synomon for the type of the grayvalues
typedef unsigned int grayvalue_t;
static_assert(std::numeric_limits<grayvalue_t>::max()<=
              std::numeric_limits<size_t>::max(),
              "grayvalue_t maximum should be smaller than size_t maximum");

// Number of rows
size_t _R;
// Number of columns
size_t _C;
// Maximum grayvalue
grayvalue_t _MAX_G;
// Pixels' grayvalues
std::vector<grayvalue_t> _pixels;

我被要求在 O(1) 中交换两个给定的行（由索引给出），这不是问题，因为我可以只使用 memcpy 并在两个连续的内存块之间替换，但问题是我还被要求在 O(1) 时间内交换两个给定的列（再次按索引），但在这种情况下，矩阵的列不是向量中连续的内存块。

/// swaps between rows r1 and r2
/// Time complexity: O(1)
void swap_rows(const size_t& r1, const size_t& r2) {

}

/// swaps between columns c1 and c2
/// Time complexity: O(1)
void swap_cols(const size_t& c1, const size_t& c2) {

}

我错过了什么吗？想得到一些帮助。

谢谢！

Answer 1

像许多其他 CS 问题一样，答案是：多一层间接。

一种选择是维护一个映射，将矩阵中的列索引映射到向量中的实际索引。也就是说，您的矩阵列不会始终按顺序存储，而行的元素将保持连续。映射开始映射 0 到 0 1 到 1，依此类推。要交换两列，您只需交换它们在地图中的条目。如果您还需要按行遍历整个数组，则需要查阅地图以了解列的顺序。

交换向量表示的矩阵中的两列

swapping two columns in a matrix represented by vector

c++

matrix

time-complexity

stdvector