在O（1）复杂度的矩阵中切换行和列

因此，对于作业，我负责的任务之一是交换2行或2列彼此，并使用构建在类类型对象中的矩阵，使用这3个参数来定义它：在O（1）复杂度的矩阵中切换行和列

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列，并且int向量数组为1,2,3,4,5,6,7,8,9，交换行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做到这一点

来源

2015-02-09 MrGuy

请告诉我们你已经试过 – 2015-02-09 13:36:23

要花几分钟，因为我只是在理论上考虑到目前为止（没有意见，如果它不是答案，对吧？：p） – MrGuy 2015-02-09 13:43:52

给定作为一个普通矢量的表示，我不相信这是可能的。 – molbdnilo 2015-02-09 13:45:15

一种方法是应用一个修改行和列到每个维度的，如：

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]) ]; 
}

这会给你的项目T在row，col但通过修改行和列的附加去参考。

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

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

和变戏法似的，下一次你访问它，行0 & 1将被切换。如果您有3 x 3矩阵或1000 x 1000，则无关紧要，修改时间始终只是在向量中交换两个整数。

来源

2015-02-09 14:04:27

请记住，这给了间接的另一层。根据掉期的频率，你宁愿交换。无论哪种方式，在尝试优化程序之前，请不要忘记运行分析器。 – Zeta 2015-02-09 14:16:04

如果这是允许的，只需添加一个转置标志。 – 2015-02-09 14:58:52

@MiloYip：如果您需要转置矩阵，这会有所帮助，但如果您想交换两个特定的行，则会有所帮助。 – Zeta 2015-02-11 06:11:34

-2

一个向量是没有间接的随机访问，所以你的问题总是O（_C）* O（2）= O（_C）在向量中的2行。

如果你想O（1）比矩阵作为行数组，所以你可以交换两行指针。交换两个cols意味着，你得到了相同的结果O（_R）。

来源

2015-02-09 14:22:10 Aitch

这仍然是O（n），因为数组上的'std :: swap'使用'swap_range'。（它会在'std :: vector >'上工作）。 – Zeta 2015-02-10 12:40:27

你是对的代码是错的。行交换可以在'T * mat [_R]上工作; for（int i = 0;/* ... * /）{mat [i] = new T [_C]; }/* ... */std :: swap（mat [3]，mat [4]）;'交换第4行和第5行 – Aitch 2015-02-10 21:49:19

Nope，如果他有两级指针，只交换两行意味着改变指向行的指针。 – 2015-02-12 06:09:03

在O（1）复杂度的矩阵中切换行和列

回答

相关问题