tem*_*def 24
让我们首先考虑问题的一个重要细节:如果两行包含不同行的列(例如,在一行中它是零,在一行中它是一行),那么就没有可能的方法两行都是一行.要看到这一点,假设行x在某些列中为零,而行y在该列中有一个.然后,如果我们不翻转该列,则行x不能全部为1,如果我们翻转列,则行y不能全部为1.因此,如果我们看一下原始矩阵并尝试考虑我们将要创建所有行的行,我们基本上只是选择一组彼此相等的行.我们的目标是选择尽可能大的相同行集,并且可以使用恰好k个翻转来制作所有行.假设可以使用恰好k翻转的所有行进行的行是"候选行".然后我们只需要在矩阵中找到最多次出现的候选行.
这样做的实际算法取决于我们是否允许两次翻转同一列.如果我们不是,则候选行是其中恰好有k个零的行.如果我们可以多次翻转同一列,那么这有点棘手.要使行全部为1,我们需要将每个零转换为1,然后需要继续花费剩余的翻转两次翻转同一列以避免将任何一个更改为零.如果k与行中的零的数量之间的差异是非负偶数,则这是真的.
使用此,我们得到以下算法:
总的来说,在mxn矩阵(m行,n列)上,我们访问每一行一次.在访问期间,我们做O(n)工作来计算零的数量,然后O(1)工作以查看它是否有效.如果是这样,则需要预期的O(n)时间来更新散列表,因为散列步骤花费O(n)时间来散列该行.这意味着我们将O(mn)时间填入表中.最后,最后一步需要时间O(m)来找到最大频率行,对于O(mn)的净运行时间,其在输入的大小上是线性的.而且,这是渐近最优的,因为如果我们花费的时间少于此,我们就无法看到矩阵元素al!
希望这可以帮助!这是一个很酷的问题!