算法问题:翻转列 [英] Algorithms question: flipping columns

问题描述

假设给定一个m x n的零和一的网格，并且想要对网格进行转换，以使最大行数完全由1组成.我们唯一允许在网格上执行的操作是选择一列，然后翻转该列中的所有零和一.我们还给了一些整数k，并且必须执行恰好个k列翻转.给定网格和k值，我们如何确定要翻转的列以最大化全为1的行数?

Suppose that we are given an m x n grid of zeros and ones and want to transform the grid so that the maximum number of rows are composed solely of ones. The only operation we are allowed to perform on the grid is picking some column and flipping all of the zeros and ones in that column. We are also given some integer k and must perform exactly k columns flips. Given the grid and the value of k, how do we determine which columns to flip to maximize the number of rows that are all ones?

我正在考虑需要做一些动态的事情，但是我无法给出一个很好的答案.有人可以帮忙吗?

I'm thinking something dynamic would need to be done, but I'm not able to arrive at a good answer. Can someone help out?

推荐答案

让我们首先考虑问题的一个重要细节:如果两行包含一列在各行之间不同(例如，一行中为零)并在一排中是一排)，那么就不可能将两排都变成一排.为此，假设某行x在某列中为零，而y在该列中为1.然后，如果我们不翻转该列，则行x不能全部为1，如果我们确实翻转该列，则行y也不能全部为1.因此，如果我们看一下原始矩阵并尝试考虑将要构成的所有行，那么实际上我们将仅选择一组彼此相等的行.然后，我们的目标是选择一组尽可能大的相同行，并且可以使用完全k次翻转将其分成所有行.假设可以完全使用k次翻转将所有行都变成一个候选行".然后，我们只需要在出现次数最多的矩阵中找到候选行即可.

Let's begin by thinking about an important detail of the problem: if two rows contain a column that differ across the rows (for example, in one row it's a zero and in one row it's a one), then there is no possible way to make both rows all ones. To see this, suppose that row x has a zero in some column and row y has a one in that column. Then if we don't flip that column, row x can't be all ones, and if we do flip the column then row y can't be all ones. Consequently, if we take a look at the original matrix and try to think about what rows we are going to make all ones, we are essentially just going to pick some set of rows that are all equal to one another. Our goal is then to pick the set of identical rows that is as large as possible and can be made into all ones using exactly k flips. Let's say that a row that can be made into all ones using exactly k flips is a "candidate row.". Then we just need to find the candidate row in the matrix that appears the greatest number of times.

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

The actual algorithm for doing this depends on whether or not we are allowed to flip the same column twice. If we aren't, then a candidate row is one that has exactly k zeros in it. If we can flip the same column multiple times, then this is a bit trickier. To make the row all ones, we would need to convert each zero to a one, then would need to keep spending the remaining flips flipping the same column twice to avoid changing any one to a zero. This is true if the difference between k and the number of zeros in the row is a nonnegative even number.

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

Using this, we get the following algorithm:

1. 维护从候选行到其频率的哈希表.
2. 对于每一行:

1. Maintain a hash table mapping from candidate rows to their frequency.
2. For each row:

1. 计算行中的数字或零.
2. 如果k与该数字之间的差是非负偶数，请通过增加该特定行的频率来更新哈希表.

在哈希表中找到总频率最高的候选行.

输出该行的频率.

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

Overall, on an m x n matrix (m rows, n columns), we visit each row once. During the visit, we do O(n) work to count the number of zeros, then O(1) work to see if it is valid. If so, it takes an expected O(n) time to update the hash table, since the hashing step takes O(n) time to hash the row. This means that we spend O(mn) time filling in the table. Finally, the last step takes time O(m) to find the max frequency row, for a net runtime of O(mn), which is linear in the size of the input. Moreover, this is asymptotically optimal, since if we spent less time than this we couldn't look at al, the matrix elements!

希望这会有所帮助！这是一个很酷的问题！

Hope this helps! This is a cool problem!

这篇关于算法问题:翻转列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！