算法问题：翻转列

Question

假设给定一个由零和一组成的mxn网格，并且希望对该网格进行变换，以使最大行数仅由一组成。我们唯一允许在网格上执行的操作是选择一列并翻转该列中的所有零和一。我们还得到了一些整数k，并且必须
精确 执行k列翻转。给定网格和k的值，我们如何确定要翻转的列以最大化全部为1的行数？

我认为需要做一些动态的事情，但是我无法给出一个好的答案。有人可以帮忙吗？

Answer 1

让我们从问题的重要细节开始思考：如果两行包含一列在各行之间都不同（例如，一行中为零，而一行中为一），那么就没有办法两行全都是。为此，假设某行x在某列中为零，而y在该列中为1。然后，如果我们不翻转该列，则行x不能全部为1，如果我们翻转该列，则行y也不能全部为1。因此，如果我们看一下原始矩阵并尝试考虑将要构成的所有行，那么实际上我们将只选择一组彼此相等的行。然后，我们的目标是选择一组尽可能大的相同行，并且可以使用完全k次翻转将其分成所有行。让’
s表示，可以完全使用k次翻转将所有行都变成一个“候选行”。然后，我们只需要在矩阵中找到出现次数最多的候选行。

执行此操作的实际算法取决于是否允许我们翻转同一列两次。如果不是，那么候选行就是其中恰好有k个零的行。如果我们可以多次翻转同一列，那么这会有些棘手。为了使行全为1，我们需要将每个零转换为1，然后需要继续花费其余翻转将同一列翻转两次，以避免将任何一个更改为零。如果k和行中零个数之间的差是非负偶数，则为true。

使用此算法，我们得到以下算法：

1. 维护从候选行到其频率的哈希表映射。
2. 对于每一行：
   1. 计算行中的数字或零。
   2. 如果k与该数字之间的差为非负偶数，请通过增加此特定行的频率来更新哈希表。
3. 在哈希表中找到总频率最高的候选行。
4. 输出该行的频率。

总体而言，在mxn矩阵（m行，n列）上，我们每行访问一次。在访问期间，我们进行O（n）工作以计算零的数量，然后O（1）工作以查看其是否有效。如果是这样，则由于哈希步骤需要O（n）时间来对行进行哈希处理，因此更新哈希表需要花费O（n）时间。这意味着我们花费O（mn）时间填写表格。最后，对于网络运行时间O（mn），最后一步需要时间O（m）来找到最大频率行，该运行时间在输入大小上是线性的。而且，这是渐近最优的，因为如果我们花费的时间少于此，我们将看不到al，即矩阵元素！

希望这可以帮助！这是一个很酷的问题！