是否有一种有效的数据结构用于行和列交换？
我有一个数字矩阵，我想：
- 交换行
- 交换列
如果我要使用指向行的指针数组，那么我可以很容易地在O(1)中的行之间切换，但是交换一列是O(N)，其中N是行的数量。
我有一个明显的感觉，没有一个双赢的数据结构，为这两个操作提供O(1)，虽然我不知道如何证明它。还是我错了？
回答 2
Stack Overflow用户
发布于 2011-08-15 07:46:32
没有完全考虑到这一点：
我认为用指针指向行的想法是正确的开始。然后，为了能够“交换”列，我只需要有另一个列大小的数组，并在每个字段中存储列当前物理位置的索引。
m =
[0] -> 1 2 3
[1] -> 4 5 6
[2] -> 7 8 9
c[] {0,1,2}现在要交换列1和2，只需将c改为{0,2,1}
当你想读第1行时，你会这样做
for (i=0; i < colcount; i++) {
print m[1][c[i]];
}Stack Overflow用户
发布于 2011-08-15 08:28:24
不过，这里只是一个随机的例子(没有体验到它到底有多好，而且很晚还没有咖啡)：
我想的是矩阵的内部应该是一个哈希表，而不是数组。
数组中的每个单元格都有三条信息：
- 单元格所在的行
- 单元格所在的列
- 单元格
的值
在我看来，这很容易用元组((i, j), v)来表示，其中(i, j)表示单元格的位置(第一行、第j列)和v。
这将是矩阵的某种正常表示形式。但是，让我们在这里严格掌握这些想法。与其将行表示为一个位置(例如，0之前是1，然后是2，然后是3等等)，不如将i看作是对应行的某种规范标识符。让我们为j做同样的事情。(在最一般的情况下，i和j可以是不受限制的，让我们假设一个简单的情况，对于don矩阵，它们将保持在0..M和0..N的范围内，但不表示单元格的实际坐标)。
现在，我们需要一种方法来跟踪一行的标识符和与该行关联的当前索引。这显然需要一个键/值数据结构，但是由于索引的数量是固定的(矩阵通常不会增长/收缩)，并且只处理积分索引，我们可以将其实现为一个固定的一维数组。对于M行的矩阵，我们可以有(在C中)：
int RowMap[M];对于第m行，RowMap[m]给出当前矩阵中行的标识符.
对于列，我们将使用相同的内容：
int ColumnMap[N];其中ColumnMap[n]是第n列的标识符.
现在回到我一开始提到的哈希表：
由于我们有完整的信息(矩阵的大小)，我们应该能够生成一个完美的散列函数(没有冲突)。这里有一种可能性(对于中等大小的数组)：
int Hash(int row, int column)
{
return row * N + column;
}如果这是哈希函数用于哈希表，那么对于大多数大小的数组，我们应该获得零冲突。这允许我们在O(1)时间内从哈希表读取/写入数据。
酷部分是将每行/列的索引与哈希表中的标识符连接起来：
// row and column are given in the usual way, in the range [0..M] and [0..N]
// These parameters are really just used as handles to the internal row and
// column indices
int MatrixLookup(int row, int column)
{
// Get the canonical identifiers of the row and column, and hash them.
int canonicalRow = RowMap[row];
int canonicalColumn = ColumnMap[column];
int hashCode = Hash(canonicalRow, canonicalColumn);
return HashTableLookup(hashCode);
}现在，由于到矩阵的接口只使用这些句柄，而不使用内部标识符，所以任意行或列的swap操作对应于RowMap或ColumnMap数组中的简单更改：
// This function simply swaps the values at
// RowMap[row1] and RowMap[row2]
void MatrixSwapRow(int row1, int row2)
{
int canonicalRow1 = RowMap[row1];
int canonicalRow2 = RowMap[row2];
RowMap[row1] = canonicalRow2
RowMap[row2] = canonicalRow1;
}
// This function simply swaps the values at
// ColumnMap[row1] and ColumnMap[row2]
void MatrixSwapColumn(int column1, int column2)
{
int canonicalColumn1 = ColumnMap[column1];
int canonicalColumn2 = ColumnMap[column2];
ColumnMap[row1] = canonicalColumn2
ColumnMap[row2] = canonicalColumn1;
}因此，这应该是一个具有O(1)访问和变异的矩阵，以及O(1)行交换和O(1)列交换。当然，即使是O(1)哈希访问也会比基于数组的访问的O(1)慢，并且将使用更多的内存，但至少行/列之间是相等的。
在你如何实现矩阵的问题上，我尽量做到不可知论，所以我写了一些C。如果你更喜欢另一种语言，我可以改变它(如果你能理解的话最好)，但我认为它是相当自我描述的，但我不能保证它的正确性，因为我实际上是一个C++的人，试图表现得像一个C人(我说过我没有喝咖啡？)就我个人而言，用一种完整的OO语言编写它可以使entrie的设计更加公正，同时也给代码带来了一些美丽，但是就像我说的，这是一个快速启动的实现。
https://stackoverflow.com/questions/7062503
复制相似问题
腾讯云开发者
