验证二维数组中所有的“1”是否构成矩形的算法

Question

验证二维数组中所有的“1”是否构成矩形的算法

javaarraysalgorithm

3

定义一个方法，给定一个二维整数数组，验证所有元素都等于1是否构成了一个矩形。

以下是我目前的想法：

public static boolean isRectangle(int[][] arr) {

// TODO: Implement this method

}

请参考下面的图片更好地理解：

public static boolean oneRectangle(int [][] a) {
    boolean rectangle=true;
    int[][] res;
    int OneinRow=0; //keeps track of how many ones there are in the row
    int OneinColoumn=0; //keeps track of how many ones there are in a coloumn

    for(int i=0; i<a.length; i++) {
        for (int j = 0; j < a[0].length; j++) {
            while (a[i][j] == 1) {
                i++;
                OneinRow++;
            }
            while (a[i][j] == 1) {
                j++;
                OneinColoumn++;
            }
        }
    }
    res = new int[OneinRow][OneinColoumn];

    for(int k=0; k<res.length; k++)
        for(int l=0; l<res[0].length; l++)
            if(res[k][l] != 1)
                rectangle = false;

    return rectangle;
}

由于某些原因，它并不能按预期工作。

f = new int[][] {
            {1,2,3,4}, //1 in position 0
            {2,1,4,5}, //1 in position 1
            {3,4,5,6}};

返回true而不是false。

我该如何修复和改进算法？

- Daniele

3

注意，res表在创建后只包含零，并且您不需要填充它任何其他内容。 - krzydyn

请尝试向我们解释您正在尝试实现的算法。 - krzydyn

@krzydyn 谢谢，确实 res 数组里为空，我会修复的。 - Daniele

你的算法不正确，甚至你的代码写得很草率。你在数列中计算1的数量，但是哪一列？ - Prince

@Prince 这也是真的...我可能得想出一个完全不同的算法。 - Daniele

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- MrSmith42 · Accepted Answer

仅按行和列计算1的数量是不够的。

我的处理方法是：

循环遍历整个数组，跟踪在每个维度中出现1的最高和最低索引。此外，统计所有看到的1的数量。

最后，1的数量必须与每个维度最高和最低索引之差的乘积相同。

对于2D数组：

int minx=Integer.MAX_VALUE;
int maxx=-1;
int miny=Integer.MAX_VALUE;
int maxy=-1;
int count=0;
for x=0...
  for y=0...
    if(1==a[x][y]{
      minx=Math.min(minx,x);
      maxx=Math.max(maxx,x);
      miny=Math.min(miny,y);
      maxy=Math.max(maxy,y);
      count ++;
    }

return count==(maxx-minx+1)*(maxy-miny+1);

PS：您可能需要添加一个检查，以确保至少有一个1。