Java 中的 M*N 矩阵的就地矩阵转置不可能吗？

Question

是否可以在 Java 中对 M*N 矩阵进行就地矩阵转置？我认为在 Java 中不可能，因为在 3*5 矩阵中，理想情况下 3*5 处的元素将与 5*3 处的元素交换，但这样的位置不存在。也就是说，C/C++，这是可能的，因为内存是连续的。

此外，还有其他算法，例如针对 M*N 矩阵发布的 here，我认为它不适用于 Java，但它与在 A[ 处交换元素有何不同i][j] 和 A[j][i] 因为上面 link 中的滚动 window 算法也需要辅助内存？

Answer 1

你是对的，它不能。在Java中，一旦创建了一个数组，它的长度就固定了。所以，如果 M 和 N 不同，则不能交换它们

Answer 2

您必须小心使用就地一词。严格来说，转置运算符 'creates' 是一个具有潜在新维度的新矩阵。对于您链接的文章，就地仅意味着对初始矩阵和最终矩阵使用相同的内存，这当然可以通过巧妙的表示来实现。

一个简单的解决方案可能是：

public class Matrix {
    private int[][] backingArray;
    private boolean transposed;
    public Matrix(int[][] _backingArray) {
        this.backingArray = _backingArray
    }

    public Matrix(int[] data, rows, columns) {
        backingArray = new int[rows][columns]
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < columns; j++)
                backingArray[i][j] = data[i*columns + j]
    }

    public int getElement(i, j) {
        if (transposed)
            return backingArray[j][i];
        return backingArray[i][j];
    }

    public void transpose() {
        transpose = !transpose;
    }
}

编辑：更正了一些错误的语法

编辑：按照 OP 问题 (?)

可以读取一维矩阵

Answer 3

如果不指定更多的上下文，你的问题并没有太大意义：算法假设数据的线性表示（由于 C[++] 等语言本质上直接访问内存，在这些情况下才有意义）。请注意，对于这种表示，您需要在数据外部表示行数和列数。因此，3x4 矩阵的数据表示同样可以用于 4x3（或 2x6 等）矩阵，您只需为 numberCols 和 numberRows 设置不同的值（在伪代码中）。所以这里的转置算法使用相同的内存分配，但是重新排序元素并重新解释行数和列数。

如果您将 Java 中的（整数）矩阵表示为 int[][]，那么您不能使用相同的算法，或者事实上任何就地转置，因为行数和该特定表示的列是固定的：Java 中的数组不可调整大小。该算法不适用，因为数据表示不是线性的。

但是如果您选择使用一维数组表示矩阵：

public class IntMatrix {

    private final int numColumns ;
    private final int numRows ;

    private final int[] data ;

    public IntMatrix(int numColumns, int numRows, int... data) {
        if (data.length != numColumns*numRows) {
            throw new IllegalArgumentException("...");
        }
        this.numColumns = numColumns ;
        this.numRows = numRows ;
        this.data = new data[numColumns * numRows] ;
        System.arrayCopy(data, 0, this.data, 0, this.data.length);
    }

    public int getElement(int row, int column) {
        return data[column*numRows+row];
    }

    public int getNumRows() {
        return numRows ;
    }

    public int getNumColumns() {
        return numColumns ;
    }
}

那么您当然可以使用完全相同的算法实现就地转置。

但是，您几乎肯定不会：您会执行以下操作：

public class IntMatrix {

    // code as before...

    public IntMatrix transpose() {
        return new Transpose(this);
    }

    private static class Transpose extends IntMatrix {
        private IntMatrix original ;
        Transpose(IntMatrix original) { 
            this.original = original ;
        }
        @Override
        public int getElement(int row, int column) {
            return original.getElement(column, row) ;
        }
        @Override
        public IntMatrix transpose() {
            return original ;
        }
        @Override
        public int getNumRows() {
            return original.getNumColumns();
        }
        @Override
        public int getNumColumns() {
            return original.getNumRows();
        }
    }
}

which（对于这个不可变的表示）创建了一个具有 O(1) 操作和 O(1) 附加内存的转置。您可以类似地创建可变表示，但需要更多的工作，而且成本可能更高，具体取决于您想要的确切行为（原始可变矩阵的转置视图等）。

Java 中的 M*N 矩阵的就地矩阵转置不可能吗？

In-place matrix transpose of an M*N matrix in Java not possible?

java

algorithm

transpose

matrix

in-place