在O（1）時間交換行或列中的二維數組C++

我的問題是，如何交換O（1）時間的二維數組的兩行或兩列？我在互聯網上搜索和我發現一個函數memcpy，但我不知道如何使用它。例如在O（1）時間交換行或列中的二維數組C++

給出的矩陣：

1 2 3 
4 5 6 
7 8 9

如果我們交換行1和行2

4 5 6 
1 2 3 
7 8 9

來源

2014-11-02 gsdf

你的老師要求你換行指針。 – nurettin 2014-11-02 06:37:54

如果它是一個二維數組，那麼您不能在O（1）中進行交換（您必須將每個元素從一行復制到另一個行，因此運行時間取決於列數，而不是O（1）除非你的數組總是有相同的列數）。你可以嘗試使用一個指針數組來替換兩行，不管長是多少，只是交換兩個指針。 – 2014-11-02 06:39:14

是否可以請用代碼解釋 – gsdf 2014-11-02 06:40:15

可以在兩個行和列使用間接陣列。換言之，以訪問一個元素i,j使用

data[rowix[i]][colix[j]]

而不是純

data[i][j]

這仍然是元件訪問的O（1）（雖然具有較大的常數因子），但也可以讓你在常量時間交換行和列（只需交換索引數組元素）。

在C++

template<int ROWS, int COLS, typename T> 
struct Mat2d { 
    T data[ROWS][COLS]; 
    int colix[COLS], rowix[ROWS]; 
    Mat2d() { 
     for (int i=0; i<ROWS; i++) { 
      for (int j=0; j<COLS; j++) { 
       data[i][j] = T(); 
      } 
     } 
     for (int i=0; i<ROWS; i++) rowix[i] = i; 
     for (int j=0; j<COLS; j++) colix[j] = j; 
    } 
    T& operator()(int i, int j) { return data[rowix[i]][colix[j]]; } 
    T operator()(int i, int j) const { return data[rowix[i]][colix[j]]; } 
    void swapRows(int i1, int i2) { std::swap(rowix[i1], rowix[i2]); } 
    void swapCols(int j1, int j2) { std::swap(colix[j1], colix[j2]); } 
};

編程每個問題可以通過添加一個間接的水平（除有太多的間接層面的問題）來解決;-)

來源

2014-11-02 06:44:48 6502

請注意額外的間接可能會影響性能。 – 2014-11-02 06:49:32

@NeilKirk：當然可以，但它仍然是O（1）元素訪問，交換行和交換列。 – 6502 2014-11-02 07:14:10

如果他提交此答案，他的老師將通過他看到：-D – JorenHeit 2014-11-02 09:13:58

在O（1）時間交換行或列中的二維數組C++

回答

相關問題