Java динамическая 2D матрица

Question

Я хотел бы создать динамическую 2D матрицу, где количество строк и столбцов неизвестно. Заполняя его, добавляя один элемент за раз. Например, 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

Вот один из вариантов, чтобы сохранить 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 
    }
}

Answer 3

Вы можете (1) использовать хэш-карту, которая отображает точки в состояния кнопок и имеет максимальное количество строк и столбцов, хранящихся в отдельных переменных;в качестве альтернативы, вы можете (2) использовать дерево и иметь один узел для каждой строки и добавлять узлы к соответствующим узлам строки для представления элементов матрицы.

Вы также можете (3) использовать упорядоченный динамический список (список массивов, связанный список и т. д.) целых чисел, где первые n биты каждого целого числа могут хранить строку, следующие n биты столбца и остальные битылюбые данные, относящиеся к состоянию кнопки.Размер n , однако, зависит от того, каковы ваши максимальные границы для числа строк и столбцов.Используйте побитовые операторы для извлечения соответствующих данных при извлечении элемента из списка.

Объем выделенной памяти будет наименьшим для (3), если используется список массивов, но в противном случае каждая запись будет иметь некоторые дополнительныеДанные, связанные с ним при добавлении дополнительных элементов, обусловлены природой структуры данных.Поиск будет быстрее всего с (1);оба (2) и (3) должны показывать O (log (n)) времени поиска, но я подозреваю, что (3) будет значительно быстрее из-за локальности данных.Из подходов (1) и (2) добавление и удаление элементов было бы быстрее всего с (1);время, необходимое для подхода (3) для добавления или удаления элемента, зависит от реализации списка.

Я уверен, что есть много других структур, которые вы могли бы использовать, но я не перечислил их здесь,но вы можете заметить, что если вы можете гарантировать, что количество строк и столбцов останется в разумных пределах, то использование статической структуры данных действительно может ускорить процесс.