在 C++ 中以 O(1) 时间交换二维数组的行或列 [英] Swap rows or columns of a 2d array in O(1) time in c++

问题描述

我的问题是如何在 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) 时间交换二维数组的行或列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！