问题描述
我的问题是如何在 O(1) 时间内交换二维数组的两行或两列?,我在互联网上搜索并找到了一个函数 memcpy 但我不知道如何使用它.例如
My question is that how can you swap two rows or two columns of a 2D array in O(1) time?,I searched on internet and i found a function memcpy but i don't know how to use it.for example
给定一个矩阵:
1 2 3
4 5 6
7 8 9
如果我们交换第 1 行和第 2 行
if we swap row 1 and row 2
4 5 6
1 2 3
7 8 9
推荐答案
您可以在行和列上使用间接数组.换句话说,要访问您使用的元素 i,j
You can use an indirect array on both rows and columns. In other words to access an element i,j
you use
data[rowix[i]][colix[j]]
代替普通
data[i][j]
这仍然是元素访问的 O(1)(尽管具有更大的常数因子),但也允许您在恒定时间内交换行和列(只需交换索引数组元素).
This is still an O(1) for element access (albeit with a larger constant factor), but also allows you to swap both rows and columns in constant time (just swap the index arrays elements).
在 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]); }
};
编程中的每一个问题都可以通过添加一个间接层来解决(除了间接层太多的问题);-)
Every problem in programming can be solved by adding an indirection level (except the problem of having too many indirection levels) ;-)
这篇关于在 C++ 中以 O(1) 时间交换二维数组的行或列的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!