java - 验证二维Array中的所有 "1"是否构成矩形的算法

Question

Define a method that, given a two-dimensional Array of Integers, verifies that all the elements equals to 1 build a rectangle.

这是我到现在为止想到的:

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。

如何修复和改进算法？

Answer 1

计算每行和每列的 1 是不够的。

我是这样做的:

遍历整个数组并跟踪每个维度中出现 1 的最高和最低索引。另外计算所有看到的 1。

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

对于二维数组:

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);

附言如果至少有一个 1，您可能想要添加一张支票。