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

数组匹配的问题

  •  
  •   qcgzxw · 2019-11-14 12:53:34 +08:00 · 4104 次点击
    这是一个创建于 1596 天前的主题,其中的信息可能已经有所发展或是发生改变。

    有数组 A:[1,2,3]

    在数组 B

    [
        [1,1,1],
        [1,2,1],
        [1,3,1],
        [1,2,3],
    ]
    

    中找出最符合的子数组[1,2,3]

    若是不存在[1,2,3],则找出任一[1,2,*]

    同理,若是不存在[1,2*],则找出任一[1,*,*]

    类似 如果我想在数组 B 中找出最符合数组 A[1,2,3,4....,n]的子数组

    11 条回复    2019-11-21 10:43:09 +08:00
    ViggoSite
        1
    ViggoSite  
       2019-11-14 13:36:55 +08:00   ❤️ 1
    最简单的办法:

    foreach 遍历 “数组 B” ,计算与 "数组 A" 元素匹配的相似度,并记录 “数组 B” 中相似度最大的元素下标 。
    hakono
        2
    hakono  
       2019-11-14 18:48:10 +08:00 via iPhone
    第一轮按照

    [0][0]
    [1][0]
    [2][0]
    [n][0]

    的顺序循环,获取到所有符合最低限度条件[1,*,*]的数组下标并记录
    然后接着遍历

    [0][1]
    [1][1]
    [2][1]
    [n][1]

    选出下符合下一次 [1,2*] 的所有下标并记录,用任何后入先出的数据借口存就行

    然后一层层循环直到记录
    最后一次找出的就是你需要的下标们
    hakono
        3
    hakono  
       2019-11-14 18:50:09 +08:00 via iPhone
    打字错误 修正

    选出下符合下一次 [1,2*] 的所有下标并记录,用任何后入先出的数据结构存就行,因为你需要的是最后一次保存的数组下标

    然后一层层循环直到结束遍历
    在那个后入先出的数据结构中,最后一次保存的下标们就是你需要的数据了
    hakono
        4
    hakono  
       2019-11-14 18:57:46 +08:00 via iPhone   ❤️ 1
    再次补充,电车打字思绪一下没整理好。。。
    第一次你需要遍历
    [0][0]
    [1][0]
    [2][0]
    [n][0]

    选出符合最低匹配条件的所有下标 a1 a2 ~ an

    然后第二次开始你就只需要在上一次匹配到的下标中匹配下一次的
    [a1][1]
    [a2][1]
    [a3][1]
    [an][1]
    之后的匹配以此类推
    php01
        5
    php01  
       2019-11-14 19:03:51 +08:00   ❤️ 1
    1.将 B 数组内的数组重新进行排序。
    2.将 A 数组进行排序。
    3.循环,用找比较差集或者交集,返回的个数,进行比较。(例,交集的话,返回的数量越多,那么相似度越高)。
    qcgzxw
        6
    qcgzxw  
    OP
       2019-11-14 21:13:45 +08:00
    @php01 首先感谢回复!
    这里是不好排序的,比如数组 A 为[1,2,1]的情况
    qcgzxw
        7
    qcgzxw  
    OP
       2019-11-14 21:14:28 +08:00
    @hakono 感谢回复,和我思路一样,目前好像没啥更优雅的方法了。
    Fangfang2019
        8
    Fangfang2019  
       2019-11-14 21:38:38 +08:00 via Android   ❤️ 1
    把一行当成一个整数,和数组 A 作差,取绝对值,最小的那个,也一定是位数最小的那个,就是最符合的,
    sdcxccy
        9
    sdcxccy  
       2019-11-14 21:59:07 +08:00
    用 B-A,有三个 0 的就是最符合的,两个 0 的其次,以此类推
    micookie
        10
    micookie  
       2019-11-20 18:12:43 +08:00 via Android
    把 a 数组转为 123 字符串
    b 数组,转为['111', '121'....]一维字符串数组
    然后去循环匹配,倒也是一种思路。
    qcgzxw
        11
    qcgzxw  
    OP
       2019-11-21 10:43:09 +08:00
    @micookie 如果 b 数组中不存在和 a 数组相同的子数组
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3692 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 00:13 · PVG 08:13 · LAX 17:13 · JFK 20:13
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.