Java - 计算 2D boolean 数组中剩余的 false

Question

我有一个 2D boolean 数组，我希望计算在对行或列具有 true 的位置应用规则后剩余的 false 数量。

如果行或列具有真值，那么我需要通过出现真值的行和列来减少 2D 数组中错误出现的次数。

例如

如果矩阵 [0] [0] 第一行和第一列中的真实欠款以及矩阵 [0] [j] 和矩阵 [i] [0] 中的所有其他条目均为假，那么我需要排除这些错误剩余错误数。

    [0],  [1]
[0] TRUE, FALSE
[1] FALSE FALSE

因此，当我应用该规则时，只有一个 false 在其行或列中没有 true，即矩阵[1][1]。

我无法概括循环迭代，它在某些情况下有效，但在其他情况下无效。下面的前两个示例是正确的，但第三个示例不正确，因为它应该是 6 而不是 4。

我可以看到的原因是，在第三个数组中，同一列(matrix3[2][4])(在matrix3中突出显示)中有一个true，它已经被淘汰了计算结果因此减少了两倍。

有没有办法可以跟踪已经从计数中取出的列和行？

public class CountRemainingFalse {
    public int countRemainingFalse (int n, boolean[][] matrix) {
        int count = n * n;

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                if (matrix[i][j]) {
                    count = count - (2 * n - 1);
                    n--;
                    break;
                }
            }
        }
        return count;
    }
}

class CountFalseRemainingApp {
    public static void main(String[] args) {
        CountRemainingFalse crf = new CountRemainingFalse();

        boolean matrix1[][] = {
                {false, false, false, false, false, false},
                {false, false, true, true, false, false},
                {false, false, true, true, false, false},
                {false, false, false, false, false, false},
                {false, false, false, false, false, false},
                {false, false, false, false, false, false} };

        boolean matrix2[][] = {
                {false, false, false, false, true, false},
                {false, false, true, true, false, false},
                {false, false, true, true, false, false},
                {false, false, false, false, false, false},
                {false, false, false, false, false, false},
                {false, false, false, false, false, false} };

        boolean matrix3[][] = {
                {false, false, false, false, true, false},
                {false, false, false, true, false, false},
                {false, false, false, false, **true**, false},
                {false, true, false, false, false, false},
                {false, false, false, false, false, false},
                {false, false, false, false, false, false} };


        System.out.println(crf.countRemainingFalse(6, matrix1));
        System.out.println(crf.countRemainingFalse(6, matrix2));
        System.out.println(crf.countRemainingFalse(6, matrix3));
    }
}

输出是:

16 // correct
9  // correct
4  // incorrect should be 6 (matrix3[0][4] was already accounted for but matrix3[2][4] also has a true)

Answer 1

您可以只执行两遍，第一部分找出哪些行和列被禁止，第二遍进行计数:

boolean[] bannedRows = new boolean[n];
boolean[] bannedColumns = new boolean[n];
for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    if (matrix[i][j]) {
      bannedRows[i] = true;
      bannedColumns[j] = true;
    }
  }
}
int count = 0;
for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    if (!bannedRows[i] && !bannedColumns[j]) {
      count++;
    }
  }
}
return count;

编辑:关于过早优化的注释:优先选择简单、明显正确的代码，而不是难以阅读和难以理解其是否正确的不必要的优化代码。一旦迫切需要优化并且您已验证此功能是导致缓慢的原因，请进行优化