algorithm - 算法问题:翻转列

Question

假设我们给出了一个0和1的M×N网格，并且希望变换网格，使得最大行数只由一个组成。我们被允许在网格上执行的唯一操作是选取某一列并翻转该列中的所有0和1我们还得到了一些整数k，并且必须精确地执行k列翻转。给定网格和k的值，我们如何确定哪些列要翻转以最大化所有行的行数？
我在想一些有活力的事情需要做，但我不能得到一个好的答案。有人能帮忙吗？

Answer 1

让我们先来思考这个问题的一个重要细节：如果两行包含一个跨行不同的列（例如，在一行中它是零，在一行中它是一），那么就不可能将两行都变成一行。要看到这一点，假设x行在某列中有一个0，y行在该列中有一个0。如果我们不翻转该列，x行就不能全部翻转，如果我们翻转该列，y行就不能全部翻转。因此，如果我们看一看原始矩阵，并尝试考虑我们将生成所有行的行，我们实际上只是选择一些行集合，这些行彼此相等。然后，我们的目标是选择尽可能大的一组相同的行，这些行可以使用精确的k个翻转生成所有行。假设一行可以完全用k个翻转生成所有行，这就是“候选行”。然后我们只需要在矩阵中找到出现次数最多的候选行。
实际的算法取决于是否允许我们翻转同一列两次。如果不是，那么候选行就是其中正好有k个零的行。如果我们可以多次翻转同一列，那么这就有点棘手了要使行全部为1，我们需要将每个0转换为1，然后需要将剩余的翻转花费在翻转同一列上两次，以避免将任何一个更改为0如果k与行中零的个数之差是非负偶数，则为真。
使用这个，我们得到以下算法：
维护从候选行到其频率的哈希表映射。
每行：
数一数行中的数字或零。
如果k与此数字之间的差是非负偶数，则通过递增此特定行的频率来更新哈希表。
在哈希表中查找总频率最大的候选行。
输出该行的频率。
总的来说，在m x n矩阵（m行，n列）上，我们访问每一行一次。在访问期间，我们做o（n）个工作来计算0的个数，然后再做o（1）个工作来查看它是否有效。如果是，则更新哈希表需要O（N）时间，因为哈希步骤对行进行哈希处理需要O（N）时间。这意味着我们花了O（mn）时间填写表格最后，对于o（mn）的净运行时，最后一步需要时间o（m）来找到最大频率行，这与输入的大小成线性关系。此外，这是渐近最优的，因为如果我们花的时间少于这个，我们就不能看al，矩阵元素！
希望这有帮助！这是个很酷的问题！