算法题 大家好，遇到一个工作中的问题，类似于算法题，就当算法题来向大家请教
一个数组 m*n(即 m 行，n 列)，值只包含 0，1 [0,1,1,1,0,0.....] [1,1,0,1,1,0.....] [0,1,0,1,0,1.....] ... [1,1,0,1,1,0.....] 给予参数 lines, columns 找出 x 行数据(x 必须大于 lines)，使得行中的数据，值为 1 的列，总列数不多于 columns 例子 1 input: [0,1,1,0,0,0] [0,1,0,1,0,0] [0,1,1,1,0,0] [1,1,0,0,1,1] lines = 2, columns = 3 output: [0,1,1,0,0,0] [0,1,0,1,0,0] 即第 1，2，3 行数据
 | 1 rrfeng Oct 10, 2017  1 按行遍历过去不就行了？也不麻烦啊，求和之后和 columns 比较即可。 更有效率的算法暂时没想到。 感觉跟二维数组没关系。 |
 | 2 mahone3297 OP @rrfeng 你可能没理解我的意思，可能我表达的不清楚 找出 x 行数据(x 必须大于 lines)，使得行中的数据，值为 1 的列， [总列数不多于 columns] 这里的总列数的意思是，所有行加起来的总列数。如： <pre> [0,1,1,0,0,0] [0,0,0,0,1,1] </pre> 这样的数据，所有行数的总列数加起来 = 4 |
| 3 mahone3297 OP |
 | 4 LuckCode Oct 10, 2017 via iPhone leetcode 有个类似的好像，建立一个 byte[]，遍历一行，对应列置 1，之后检查 1 的个数，不够则下一行重复上述操作，如果只是找出一个满足的结果而不是所有情况的话，应该就可以了吧。 |
 | 5 Finest Oct 10, 2017  1 找出 x 行数据(x 必须大于 lines) 这里的 x 是大于等于 lines 吧？你给的 output 结果 x 不是等于 2 吗？ |
 | 6 tomatoz Oct 10, 2017 via Android 你说的总列数是想找到多行在一维上的"投影"，是吗 ，创造一个全是 0 的行，假如就叫 new_line 吧，遍历数组，每行都做这样的操作: 每个元素和 new_line 对应元素按位取或，生成的结果覆盖 new_line，然后对 new_line 里"1"的个数计数。至于 x 什么的你自己应该会判断吧。 |
 | 7 RecursiveG Oct 10, 2017 1 1. 选中所有行 2. 统计选中行组成的矩阵中，每一列有多少“ 1 ”。选择“ 1 ”最少的一列，将这一列为“ 1 ”的行取消选择。 3. 重复步骤 2 直到含“ 1 ”列数量满足 columns 要求 4. 检查选中行数量是否满足 lines 要求，满足则有解，不满足则无解 |
| 8 mahone3297 OP |
| 9 mahone3297 OP @RecursiveG * 非常感谢您的答案！你的答案，确实给出了一个解。但，好像不是最优解感觉。 * 你的算法，和下面的算法类似（下面的算法是我目前的算法），你看看，是不是 * 将所有行，按列，值相加，得到一个数组，值为列出现的次数。比如 input: [0,1,1,0,0,0] [0,1,0,1,0,0] [0,1,1,1,0,0] [1,1,0,0,1,1] 得到数组[1,4,2,2,1,1] * 从大到小的顺序，取出前 columns 列，假如 columns=3，则前 3 位为 4，2，2，分别是第 2，3，4 列 * 遍历原二维数组，看每行为 1 的值是否只在上面的 2，3，4 列，得到新二维数组 * 判断新二维数组是否满足 lines 的要求，满足则是解，不满足则无解 |
 | 10 minami Oct 10, 2017 如果 n 不大的话，由于每行数据其实是一个非负整数的二进制表示，则原矩阵可以按行转化为 m 维的向量。利用按位与的性质，可以用 DP 解决。 求二进制数中 1 的个数有快速算法，甚至可以用 CPU 指令解决，见 https://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html。 |
| 12 RecursiveG Oct 10, 2017 1 不一样，考虑如下情况 [1,1,0,1,0,0] [1,0,1,0,1,0] [0,1,1,0,0,1] columns=3, lines=1 你的算法： [2,2,2,1,1,1] 取 1，2，3 列，没有行满足要求，输出无解。 我的算法： 全选所有行:[2,2,2,1,1,1] 选择第 4 列，剔除第 1 行，更新各列和:[1,1,2,0,1,1] 选择第 1 列，剔除第 2 行，更新各列和:[0,1,1,0,0,1] 已满足 columns 要求，并且目前仍有第 3 行被选中 满足 lines 要求，输出有解。 算法复杂度目测 O(m(n^2)) |
| 13 rrfeng Oct 10, 2017 via Android 哦，我说不可能这么简单... |
 | 14 mkeith Oct 10, 2017 二进制 按位异或 运算呢? |
| 15 mahone3297 OP @minami 我不是要求 1 的个数。我期望的 output，是行 @RecursiveG 确实，好像你的算法更优！有一些证明吗？你的算法确实比我的好，或者你的算法，找到的就是最优解？你的这个算法，有通用模型吗？你是如何想到的？还是直接遇到过类似的题目？ |
| 16 minami Oct 10, 2017 via Android 1 @mahone3297 你没懂我的意思，你 dp 后就可以取出满足要求的所有区间。求 1 的个数是为了求你所谓的总列数，这是等价问题。 |
| 17 RecursiveG Oct 11, 2017 1 @mahone3297 好吧我的方法也是错的。反例： [0,1,1,1,0,0,0] [1,0,1,1,0,0,0] [1,1,0,1,0,0,0] [1,1,1,0,0,0,0] [0,0,0,0,1,1,1] [0,0,0,0,1,1,1] lines=2 columns=3 @minami 求 DP 方程看看？ |
| 18 mahone3297 OP @RecursiveG 嗯，我昨天发完贴，又想，你和我，某种程度上是一样的。我从大往小，你从小往大。某种程度上，都会造成，a 适用，b 不适用的问题 @minami 嗯，麻烦再多说点，给 DP 方程看看 |
| 19 minami Oct 11, 2017 @mahone3297 #18 你要找的 x 行数据是连续的还是不连续的？而且我看 12L 和 17L 的讨论又糊涂了，RecursiveG 举得两个例子不是都无解么 |
| 20 minami Oct 12, 2017 |
Select Language