工作中算法题请教，二维数组计算

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2612 天前的主题，其中的信息可能已经有所发展或是发生改变。

算法题大家好，遇到一个工作中的问题，类似于算法题，就当算法题来向大家请教

一个数组 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 条附言 · 2017-10-10 13:47:52 +08:00

针对大家的一些问题，更新一下题目

一个数组 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
这里的总列数的意思是，所有行加起来的总列数。如：
[0,1,1,0,0,0]
[0,0,0,0,1,1]
这样的数据，所有行数的总列数加起来 = 4

[0,1,1,0,0,0]
[0,0,1,0,1,0]
这样的数据，所有行数的总列数加起来 = 3

例子 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 行数据

columns

lines

算法

20 条回复 • 2017-10-12 01:36:49 +08:00

rrfeng

2017-10-10 12:03:42 +08:00

按行遍历过去不就行了？也不麻烦啊，求和之后和 columns 比较即可。

更有效率的算法暂时没想到。

感觉跟二维数组没关系。

mahone3297

2017-10-10 12:11:13 +08:00

@rrfeng 你可能没理解我的意思，可能我表达的不清楚

找出 x 行数据(x 必须大于 lines)，使得行中的数据，值为 1 的列， [总列数不多于 columns]
这里的总列数的意思是，所有行加起来的总列数。如：
<pre>
[0,1,1,0,0,0]
[0,0,0,0,1,1]
</pre>
这样的数据，所有行数的总列数加起来 = 4

mahone3297

2017-10-10 12:13:22 +08:00

@rrfeng
[0,1,1,0,0,0]
[0,0,1,0,1,0]
这样的数据，所有行数的总列数加起来 = 3

LuckCode

2017-10-10 12:28:26 +08:00 via iPhone

leetcode 有个类似的好像，建立一个 byte[]，遍历一行，对应列置 1，之后检查 1 的个数，不够则下一行重复上述操作，如果只是找出一个满足的结果而不是所有情况的话，应该就可以了吧。

hand515

2017-10-10 13:06:25 +08:00

找出 x 行数据(x 必须大于 lines)

这里的 x 是大于等于 lines 吧？你给的 output 结果 x 不是等于 2 吗？

tomatoz

2017-10-10 13:20:17 +08:00 via Android

你说的总列数是想找到多行在一维上的"投影"，是吗
，创造一个全是 0 的行，假如就叫 new_line 吧，遍历数组，每行都做这样的操作: 每个元素和 new_line 对应元素按位取或，生成的结果覆盖 new_line，然后对 new_line 里"1"的个数计数。至于 x 什么的你自己应该会判断吧。

RecursiveG

2017-10-10 13:40:49 +08:00

1. 选中所有行
2. 统计选中行组成的矩阵中，每一列有多少“ 1 ”。选择“ 1 ”最少的一列，将这一列为“ 1 ”的行取消选择。
3. 重复步骤 2 直到含“ 1 ”列数量满足 columns 要求
4. 检查选中行数量是否满足 lines 要求，满足则有解，不满足则无解

mahone3297

2017-10-10 13:55:48 +08:00

@hand515 嗯，大于等于，我的描述不正确
@tomatoz 嗯，你说的对。但你说的这个 new_line，解决的只是其中的一步（即找出所有行的总列数），这个题最后的结果，不是找列，是需要返回行

mahone3297

2017-10-10 14:03:16 +08:00

@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 的要求，满足则是解，不满足则无解

minami

2017-10-10 14:13:44 +08:00

如果 n 不大的话，由于每行数据其实是一个非负整数的二进制表示，则原矩阵可以按行转化为 m 维的向量。利用按位与的性质，可以用 DP 解决。
求二进制数中 1 的个数有快速算法，甚至可以用 CPU 指令解决，见
https://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html。

minami

2017-10-10 14:14:47 +08:00

@minami #10 修正，是按位或

RecursiveG

2017-10-10 14:19:16 +08:00

不一样，考虑如下情况
[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))

rrfeng

2017-10-10 14:25:00 +08:00 via Android

哦，我说不可能这么简单...

mkeith

2017-10-10 15:29:15 +08:00

二进制按位异或运算呢?

mahone3297

2017-10-10 16:32:00 +08:00

@minami 我不是要求 1 的个数。我期望的 output，是行
@RecursiveG 确实，好像你的算法更优！有一些证明吗？你的算法确实比我的好，或者你的算法，找到的就是最优解？你的这个算法，有通用模型吗？你是如何想到的？还是直接遇到过类似的题目？

minami

2017-10-10 18:31:23 +08:00 via Android

@mahone3297 你没懂我的意思，你 dp 后就可以取出满足要求的所有区间。求 1 的个数是为了求你所谓的总列数，这是等价问题。

RecursiveG

2017-10-11 04:04:45 +08:00

@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 方程看看？

mahone3297

2017-10-11 09:51:31 +08:00

@RecursiveG 嗯，我昨天发完贴，又想，你和我，某种程度上是一样的。我从大往小，你从小往大。某种程度上，都会造成，a 适用，b 不适用的问题

@minami 嗯，麻烦再多说点，给 DP 方程看看

minami

2017-10-11 23:59:00 +08:00

@mahone3297 #18 你要找的 x 行数据是连续的还是不连续的？而且我看 12L 和 17L 的讨论又糊涂了，RecursiveG 举得两个例子不是都无解么

minami

2017-10-12 01:36:49 +08:00

@minami #19 https://gist.github.com/anonymous/18b32d9980e157e6b89706d6aeac7929
Show the code