如何使用分而治之在二维数组中查找特定列

Question

我正在尝试解决分而治之的问题，在该问题中，我有一个填充了true和false的二维布尔数组。我正在尝试找到仅在其中的特定列。查找此列的另一种方法是查找仅包含1个真实索引而其余为false的行。我必须找到小于O（N ^ 2）

的解决方案

二维数组样本：

F F T F
F T T T
F F T T
T F T F

Answer 1

我的想法是使用递归方法在每次递归中逐列进行，直到找到所有T或不带界线为止。逻辑运算符AND可以评估每个单独列上的行…

int getTrueColumn(boolean[][] booleansTable, int index) {
    if (index >= booleansTable[0].length)
        return -1;

    boolean trueColumn = true;
    int i = 0;

    while(trueColumn && i < booleansTable.length) {
        trueColumn &= booleansTable[i][index];
        i++;
    }
    return trueColumn ? index : getTrueColumn(booleansTable, index + 1);
}

我无法想象，它可能具有比O（n²）更好的时间复杂度。最后，您需要检查所有n行，以查看最后一行是否为false，然后对n列重复相同的过程（最坏的情况是最后一列）。如果我错了，在这种情况下我会很乐意学习！