Java动态二维矩阵

Question

我想创建一个动态二维矩阵，其中行数和列数未知。通过一次添加一个元素来填充它。例如，第1次按钮点击 = M[1][1]（此时矩阵只包含该元素），则M[1][2]、[1][3]....等。

Answer 1

使用集合来做到这一点。例如：

List<List<Integer>> dynamic2D = new ArrayList<List<Integer>>();

dynamic2D.add(new ArrayList<Integer>());
dynamic2D.add(new ArrayList<Integer>());
dynamic2D.add(new ArrayList<Integer>());

dynamic2D.get(0).add(5);
dynamic2D.get(0).add(6);
dynamic2D.get(0).add(7);

System.out.println(dynamic2D.get(0).get(0)); // 5
System.out.println(dynamic2D.get(0).get(1)); // 6
System.out.println(dynamic2D.get(0).get(2)); // 7

Answer 2

这里有一个可以考虑的选项，可以让您的二维数组保持快速处理。它以固定大小的 int[][] 数组开始，并且仅根据需要增长：

public class DynamicMatrix2D {
    private int[][] matrix = new int[5][5];

    public void set(int x, int y, int value) {
        if (x >= matrix.length) {
            int[][] tmp = matrix;
            matrix = new int[x + 1][];
            System.arraycopy(tmp, 0, matrix, 0, tmp.length);
            for (int i = x; i < x + 1; i++) {
                matrix[i] = new int[y];
            }
        }

        if (y >= matrix[x].length) {
            int[] tmp = matrix[x];
            matrix[x] = new int[y + 1];
            System.arraycopy(tmp, 0, matrix[x], 0, tmp.length);
        }

        matrix[x][y] = value;
    }

    public int get(int x, int y) {
        return x >= matrix.length || y >= matrix[x].length ? 0 : matrix[x][y];
    }

    public static void main(String[] args) {
        DynamicMatrix2D matrix2d = new DynamicMatrix2D();

        matrix2d.set(1, 1, 1);     // set (1, 1) to 1
        matrix2d.set(10, 10, 2);   // set (10, 10) to 2
        matrix2d.set(100, 100, 3); // set (100, 100) to 3

        System.out.println(matrix2d.get(1, 1));     // outputs 1
        System.out.println(matrix2d.get(10, 10));   // outputs 2
        System.out.println(matrix2d.get(100, 100)); // outputs 3 
    }
}

Answer 3

您可以（1）使用哈希映射，将点映射到按钮状态，并将最大行数和列数存储在单独的变量中；或者，您可以 (2) 使用一棵树，每一行都有一个节点，并将节点添加到相应的行节点来表示矩阵条目。

您还可以 (3) 使用整数的有序动态列表（数组列表、链接列表等），其中每个整数的前 n 位可以存储行，下一个 n 位为列，其余位为与按钮状态相关的任何数据。但是，n 的大小取决于行数和列数的最大界限。从列表中检索元素时，使用按位运算符提取相关数据。

如果使用数组列表，则分配的内存量对于 (3) 来说将是最少的，但否则，由于数据结构的性质，当您添加额外元素时，每个条目都会有一些与之关联的额外数据。使用 (1) 搜索速度最快； (2) 和 (3) 都应该表现出 O(log(n)) 搜索时间，但我怀疑由于数据局部性，(3) 会明显更快。在方法（1）和（2）中，添加和删除元素的速度最快的是（1）；方法（3）添加或删除元素所需的时间取决于列表的实现。

我确信还有很多其他结构可供您使用，但我没有在此处列出，但您可能需要注意，如果您可以保证行数和列数保持在合理的范围内，那么使用静态数据结构确实可以加快速度。