两个数字集合,找出满足差在一定范围内且唯一匹配的一对数

发布于 2022-08-31 20:48:45 字数 138 浏览 11 评论 0

唯一匹配是指————任何找出来的一对数中,位于一个集合中的数只能和另一个集合中的唯一 一个数匹配,有多个匹配组合的话全部舍弃。
相当于找出匹配的数据后再查重,最后得出的是两个集合中满足条件且唯一对应的匹配数的集合。
假设各集合数据量百万个吧。

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

梦晓ヶ微光ヅ倾城 2022-09-07 20:48:45

有意思。

先排序,然後遍歷,同時刪掉兩個集合中不能唯一匹配的數會簡單一些。這樣兩個集合中剩下的數目一樣,剛好按順序一一對應。

不算排序,複雜度大致是 O(mn)。m 爲範圍。

想不到複雜度更低的方法了 ╮(╯_╰)╭

僞代碼(javascript2):

javascript2for (let c1 of sortedSet1) {
    for (let c2 of sortedSet2) {
        if (Math.abs(c1 - c2) < range) {
            sortedSet1.delete(c1);
            sortedSet2.delete(c2);
        }
    }
}
~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文