V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
mahone3297
V2EX  ›  算法

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

  •  
  •   mahone3297 · 2017-10-10 11:45:14 +08:00 · 3746 次点击
    这是一个创建于 2361 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    一个数组 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 行数据
    20 条回复    2017-10-12 01:36:49 +08:00
    rrfeng
        1
    rrfeng  
       2017-10-10 12:03:42 +08:00   ❤️ 1
    按行遍历过去不就行了?也不麻烦啊,求和之后和 columns 比较即可。

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

    感觉跟二维数组没关系。
    mahone3297
        2
    mahone3297  
    OP
       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
        3
    mahone3297  
    OP
       2017-10-10 12:13:22 +08:00
    @rrfeng
    [0,1,1,0,0,0]
    [0,0,1,0,1,0]
    这样的数据,所有行数的总列数加起来 = 3
    LuckCode
        4
    LuckCode  
       2017-10-10 12:28:26 +08:00 via iPhone
    leetcode 有个类似的好像,建立一个 byte[],遍历一行,对应列置 1,之后检查 1 的个数,不够则下一行重复上述操作,如果只是找出一个满足的结果而不是所有情况的话,应该就可以了吧。
    hand515
        5
    hand515  
       2017-10-10 13:06:25 +08:00   ❤️ 1
    找出 x 行数据(x 必须大于 lines)

    这里的 x 是大于等于 lines 吧?你给的 output 结果 x 不是等于 2 吗?
    tomatoz
        6
    tomatoz  
       2017-10-10 13:20:17 +08:00 via Android
    你说的总列数是想找到多行在一维上的"投影",是吗
    ,创造一个全是 0 的行,假如就叫 new_line 吧,遍历数组,每行都做这样的操作: 每个元素和 new_line 对应元素按位取或,生成的结果覆盖 new_line,然后对 new_line 里"1"的个数计数。至于 x 什么的你自己应该会判断吧。
    RecursiveG
        7
    RecursiveG  
       2017-10-10 13:40:49 +08:00   ❤️ 1
    1. 选中所有行
    2. 统计选中行组成的矩阵中,每一列有多少“ 1 ”。选择“ 1 ”最少的一列,将这一列为“ 1 ”的行取消选择。
    3. 重复步骤 2 直到含“ 1 ”列数量满足 columns 要求
    4. 检查选中行数量是否满足 lines 要求,满足则有解,不满足则无解
    mahone3297
        8
    mahone3297  
    OP
       2017-10-10 13:55:48 +08:00
    @hand515 嗯,大于等于,我的描述不正确
    @tomatoz 嗯,你说的对。但你说的这个 new_line,解决的只是其中的一步(即找出所有行的总列数),这个题最后的结果,不是找列,是需要返回行
    mahone3297
        9
    mahone3297  
    OP
       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
        10
    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
        11
    minami  
       2017-10-10 14:14:47 +08:00
    @minami #10 修正,是按位或
    RecursiveG
        12
    RecursiveG  
       2017-10-10 14:19:16 +08:00   ❤️ 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))
    rrfeng
        13
    rrfeng  
       2017-10-10 14:25:00 +08:00 via Android
    哦,我说不可能这么简单...
    mkeith
        14
    mkeith  
       2017-10-10 15:29:15 +08:00
    二进制 按位异或 运算呢?
    mahone3297
        15
    mahone3297  
    OP
       2017-10-10 16:32:00 +08:00
    @minami 我不是要求 1 的个数。我期望的 output,是行
    @RecursiveG 确实,好像你的算法更优!有一些证明吗?你的算法确实比我的好,或者你的算法,找到的就是最优解?你的这个算法,有通用模型吗?你是如何想到的?还是直接遇到过类似的题目?
    minami
        16
    minami  
       2017-10-10 18:31:23 +08:00 via Android   ❤️ 1
    @mahone3297 你没懂我的意思,你 dp 后就可以取出满足要求的所有区间。求 1 的个数是为了求你所谓的总列数,这是等价问题。
    RecursiveG
        17
    RecursiveG  
       2017-10-11 04:04:45 +08:00   ❤️ 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 方程看看?
    mahone3297
        18
    mahone3297  
    OP
       2017-10-11 09:51:31 +08:00
    @RecursiveG 嗯,我昨天发完贴,又想,你和我,某种程度上是一样的。我从大往小,你从小往大。某种程度上,都会造成,a 适用,b 不适用的问题

    @minami 嗯,麻烦再多说点,给 DP 方程看看
    minami
        19
    minami  
       2017-10-11 23:59:00 +08:00
    @mahone3297 #18 你要找的 x 行数据是连续的还是不连续的?而且我看 12L 和 17L 的讨论又糊涂了,RecursiveG 举得两个例子不是都无解么
    minami
        20
    minami  
       2017-10-12 01:36:49 +08:00
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   994 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 20:06 · PVG 04:06 · LAX 13:06 · JFK 16:06
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.