如何根据数组中的元素用正方形包含二维数组的区域？

Question

举个简单的例子，我的问题是这样的：

我有一个包含 1 和 0 的 二维数组 。大多数网格是 0s，但也有一些 1s 分散在那里。我想通过查找 top-left 和 bottom-right[=30] 的索引来创建一个包含所有 1 而没有任何不必要的 space 的正方形=] 这样一个正方形的元素。

我希望这有助于形象化我正在尝试做的事情：

0 1 2 3 4 5 6 7 8 9 A 0 0 0 0 0_0_0_0_0 0 B 0 0 0 0|0 0 1 0 0|0 C 0 0 0 0|1 1 1 0 0|0 D 0 0 0 0|0 0 0 1 1|0 E 0 0 0 0|1 0 0 0 0|0 F 0 0 0 0|0_1_0_0_0|0 G 0 0 0 0 0 0 0 0 0 0 H 0 0 0 0 0 0 0 0 0 0

所以在这种情况下，我想找到 B4 和 F8 的索引。我在 Java 工作，想要一个不使用集合的解决方案。

Answer 1

您必须遍历给定数组并跟踪 minimum 和 maximum 索引（外部数组和内部数组）值为 1.

的元素

在Java中需要先初始化一个局部变量才能访问它。因此，所有 max 变量都以 -1 的值启动，并且 max 变量具有相应的 数组长度 （无效索引).

public static void main(String[] args) {
    int[][] grid = {
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
            {0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 1, 1, 0},
            {0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};

    int minRow = grid.length;
    int minCol = grid[0].length;
    int maxRow = -1;
    int maxCol = -1;
    for (int row = 0; row < grid.length; row++) {
        for (int col = 0; col < grid[0].length; col++) {
            if (grid[row][col] == 0) continue; // skipping this element

            minRow = Math.min(row, minRow);
            minCol = Math.min(col, minCol);
            maxRow = Math.max(row, maxRow);
            maxCol = Math.max(col, maxCol);
        }
    }

    if (maxRow == -1) {
        System.out.println("The given array has no elements with value of 1");
    } else {
        System.out.println("minRow: " + minRow);
        System.out.println("minCol: " + minCol);
        System.out.println("maxRow: " + maxRow);
        System.out.println("maxCol: " + maxCol);
    }
}

输出

minRow: 1
minCol: 4
maxRow: 5
maxCol: 8

Sidenote：从object-oriented设计的角度来看，这个功能可以封装在一个 class，比方说MatrixStatistics。这将允许您存储这些数据，并且可能类似于元素计数，或 object 中每个子数组的频率直方图。可以从方法 return 编辑（ 如您所知，不可能从方法 return 多个值 ），或用作字段。作为此类可变对象关心统计数据的 JDK 的示例，您可以查看 IntSummaryStatistics class.

如何根据数组中的元素用正方形包含二维数组的区域？

How can I encompass a region of a 2D Array with a square based on the elements in the array?

java

arrays

algorithm

multidimensional-array