在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）複雜度的矩陣中切換行和列

回答

相關問題