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

一组已知长度的数,按预设百分比分成两组 ab,这两组中其中一组 a 可以一对多另一组 b 的数,即可以 a 中某个数可以快速匹配另一组的几个数

  •  
  •   iloooo · 2023-10-31 16:12:04 +08:00 · 802 次点击
    这是一个创建于 388 天前的主题,其中的信息可能已经有所发展或是发生改变。

    大佬们,求助此情形需要使用什么算法,可以快速确立 ab 的对应关系

    确认算法后,是否可以使用 java 来设计下,要求高性能,感激~

    9 条回复    2023-10-31 20:09:47 +08:00
    leavebody
        1
    leavebody  
       2023-10-31 16:29:41 +08:00
    是我的理解能力太差,还是楼主的表达能力一言难尽。。。
    jifengg
        2
    jifengg  
       2023-10-31 16:34:59 +08:00
    @leavebody 别怀疑自己。

    另外,楼主,在不清楚你的需求的前提下,如果你不限制内存使用,那么就用 Map 把,o(1)时间复杂度
    edward1987
        3
    edward1987  
       2023-10-31 16:36:36 +08:00
    看不懂+1 ,还是具体拿一些数字举例吧
    iloooo
        4
    iloooo  
    OP
       2023-10-31 17:06:12 +08:00
    @edward1987 @jifengg @leavebody 补充补充:
    int[] numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    double percentage = 0.6; // 60%的数据分到 a 组,40%的数据分到 b 组

    最终想得到效果是:
    Map:{
    7 -> 1,2
    8 ->3,4
    9 -> 5
    10 -> 6
    }
    因为比例关系,两个数组肯定有个多有个少,少的来 1 对多
    leavebody
        5
    leavebody  
       2023-10-31 17:09:40 +08:00
    @iloooo 直接用你这个 map 的数据结构有什么问题吗,构造过程时间复杂度 O(n),查询时间复杂度 O(1)
    iloooo
        6
    iloooo  
    OP
       2023-10-31 17:21:57 +08:00
    @leavebody 业务上每个数字将涉及一次 “存对应关系” 和一次 “取此此数字对应其他数字”,时间维度是确认存比取早;不过构造对应关系这边有问题,数字多线程每秒产生的,归类成数组时是每分钟。所以构造时其实想得到的是一个计算标识,使得下个数字存取时动态知道了自己的存取逻辑,哈哈哈 有点绕
    iloooo
        7
    iloooo  
    OP
       2023-10-31 17:23:41 +08:00
    @leavebody 当然也可以把业务搞简单,所有此数组的取都必须延迟 1 分钟,这样取的时候数组对应关系已确认了,不过尽量想找到不延迟的办法
    edward1987
        8
    edward1987  
       2023-10-31 17:47:47 +08:00
    大概知道你啥意思了。
    先根据比例来算出多少个数字 x 算一个循环。 比如 40% 那就是 3:2 ,就是 5 个数字一个循环。x=5 。
    然后进来一个数 n ,算出它在那个循环基数先,比如 3 在第一个循环,8 则是在第二个循环。但是对应 3 和 8 对应的取数逻辑是一致的。
    1->2 , 3->4, 1->5
    如果是第二个循环则是
    6->7,8->9,6->10

    当进来一个数之后 比如 24 ,循环 bias 是 20 , 取数逻辑同 4 ,所以是 23->24
    dahuahua
        9
    dahuahua  
       2023-10-31 20:09:47 +08:00
    我应该理解你的需求了,O(1)复杂度的公式就能计算出来。设分组后两边数组的长度分别为 a, b(a > b),实际上 a - b 就能得出能够一一对应的个数,反之能推算出 a 组中需要二次分组的长度,那么接下来就是要知道每个分组的长度是多少,这个也很好算,除一下就行了,最后再把数组的下标跟 a,b 的关系梳理一下就行了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5305 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 09:01 · PVG 17:01 · LAX 01:01 · JFK 04:01
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.