是否有行和列交換的高效數據結構？

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人一樣行事（並且我提到我沒有咖啡？）。就個人而言，用完整的面嚮對象語言編寫代碼會使得設計更加公正，並且使代碼具有一定的美感，但正如我所說的那樣，這是一個很快的實現。