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


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

python matlab 数据 数据结构和算法

pology 11 years, 11 months ago

有意思。

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

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

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

僞代碼(javascript2):


 javascript2


 for (let c1 of sortedSet1) {
    for (let c2 of sortedSet2) {
        if (Math.abs(c1 - c2) < range) {
            sortedSet1.delete(c1);
            sortedSet2.delete(c2);
        }
    }
}

zsl1005 answered 11 years, 11 months ago

Your Answer