是否有行和列交换的高效数据结构？

Question

我有数字矩阵，我希望能够：

1. 交换行
2. 交换柱

如果我用指针数组的行，然后我可以轻松地在O（1）中的行之间切换，但交换列是O（N），其中N是行数。

我有一个独特的感觉，没有一个双赢的数据结构，为两个操作提供O（1），但我不知道如何证明它。或者我错了？

Answer 1

，而不必以为这完全是通过：

我想用指针来排你的想法是正确的开始。然后，为了能够“交换”列，我只需要另一个具有列数大小的数组，并在每个字段中存储列当前物理位置的索引。

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

Answer 2

只是一个随机虽然在这里（没有经验，这真的工作得如何，并且它是一个深夜没有咖啡）：

我在想的是矩阵的内部是散列表，而不是阵列。

阵列内的每个单元具有三个信息：

1. 其中细胞驻留
2. 其中细胞驻留
3. 单元格的值的列中的行

在我看来，这很容易用元组((i, j), v)表示，其中(i, j)表示单元（第i行，第j列）的位置，并且v

这将是一个有点正常的矩阵表示。但是让我们在这里将这些想法提炼出来。而不是i表示该行作为一个位置（即在3之前的2之前的1之前的0等），让我们考虑i是其相应行的某种标准标识符。让我们来做j。 （尽管在最一般的情况下，i和j可以不受限制，我们假设一个简单的情况，对于一个M×N矩阵它们将保持在范围[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）排交换a nd O（1）列交换。当然，即使是O（1）散列访问也会比基于数组的访问的O（1）慢，并且会使用更多的内存，但至少在行/列之间存在相等性。

我试图尽可能地不可能知道你是如何实现你的矩阵的，所以我写了一些C语言。如果你更喜欢另一种语言，我可以改变它（如果你理解，这将是最好的） ，但我认为这是非常自我描述性的，尽管我不能确保它的正确性就C来说，因为我实际上是一个C++的人，现在想要像C人一样行事（并且我提到我没有咖啡？）。就个人而言，用完整的面向对象语言编写代码会使得设计更加公正，并且使代码具有一定的美感，但正如我所说的那样，这是一个很快的实现。