Java动态2D矩阵

Question

l想创建一个动态2D矩阵，其中行和列的数量未知。通过在当时添加一个元素来填充它。例如，第一个按钮click = 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

你可以（1）使用一个散列映射它映射指向按钮状态，并且具有存储在单独的变量的行和列的最大数量;或者，您可以（2）使用树并为每一行都有一个节点，并将节点添加到相应的行节点以表示矩阵条目。

你也可以（3）使用整数，其中每个整数的第一Ñ位可以存储行的有序，动态列表（数组列表，链接列表等），下一Ñ位该列以及与该按钮的状态有关的其余位的任何数据。然而，n的大小取决于行数和列数的最大范围。当您从列表中检索元素时，使用按位运算符来提取相关数据。

如果使用数组列表，则分配的内存量将最少（3），否则，由于数据结构的性质，每个条目在添加额外元素时都会有一些额外的数据。 （1）的搜索速度最快; （2）和（3）都应该显示O（log（n））的搜索时间，但是由于数据的局部性，我会怀疑（3）会快得多。在方法（1）和（2）中，添加和删除元素的速度最快（1）;方法（3）添加或移除元素所用的时间取决于列表的实现。

我敢肯定有很多其他的结构可以使用，我没有在这里列出，但是您可能要注意的是，如果您可以保证行数和列数保持在合理范围内，那么使用静态数据结构可以真正加快速度。

Answer 3

这里有一个选项可以考虑保持你的2D阵列快速处理。它始于的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 
    } 
}