方法一:蛮力法 最简单的方法就是遍历两个集合,针对集合中的每个元素判断是否有交集,如果有,则求出它们的交集,实现代码如下:
package main
import(
"fmt"
)
typeMySetstruct{
Min int
Max int
}
func getIntersectionSub(s1, s2 *MySet)*MySet{
if s1.Min<s2.Min {
if s1.Max<s2.Min {
returnnil
} elseif s1.Max<=s2.Max
return&MySet {s2.Min, s1.Max}
}else{
return&MySet {s2.Min, s2.Max}
}
}elseif s1.Min<s2.Max {
if s1.Max<=s2.Max {
return&MySet{s1.Min, s1.Max}
}else{
return&MySet{s1.Min, s2.Max}
}
}
returnnil
}
func getIntersection1(l1, l2 []*MySet)[]*MySet{
result:=make([]*MySet, 0)
for_, v1:=range l1 {
for_, v2:=range ;2 {
s:=getIntersectionSub(v1, v2)
if s!=nil {
result=append(result, s)
}
}
}
return result
}
func main() {
l1:=[]*MySet{
&MySet{4, 8},
&MySet{9, 13},
}
l2:=[]*MySet{
&MySet {6, 12},
}
fmt.Println("暴力法")
result:=getlntersectionl (l1, l2)
for_, v:=range result{
fmt.Println("[", v.Min, ", ", v.Max, "]")
}
}
代码运行结果为:
[6,8]
[9,12]
算法性能分析: 这种方法的时间复杂度为O(n
2)。
方法二:特征法 上述这种方法显然没有用到集合有序的特点,因此,它不是最佳的方法。假设两个集合为s1,s2。当前比较的集合为s1[i]和s2[j],其中,i与j分别表示的是集合s1与s2的下标。可以分为如下几种情况:
(1)s1集合的下界小于s2的上界,如下图所示:
在这种情况下,s1[i]和s2[j]显然没有交集,那么接下来只有s1[i+1]与s2[j]才有可能会有交集。
(2)s1的上界介于s2的下界与上界之间
在这种情况下,s1[i]和s2[j]有交集(s2[j]的下界和s1[i]的上界),那么接下来只有s1[i+1]与s2[j]才有可能会有交集。
(3)s1包含s2
在这种情况下,s1[i]和s2[j]有交集(交集为s2[j]),那么接下来只有s1[i]与s2[j+1]才有可能会有交集。
(4)s2包含s1
在这种情况下,s1[i]和s2[j]有交集(交集为s1[i]),那么接下来只有s1[i+1]与s2[j]才有可能会有交集。
(5)s1的下界介于s1的下界与上界之间
在这种情况下,s1[i]和s2[j]有交集(交集为s1[i]的下界和s2[j]的上界),那么接下来只有s1[i]与s2[j+1]才有可能会有交集。
(6)s2的上界小于s1的下界
在这种情况下,s1[i]和s2[j]显然没有交集,那么接下来只有s1[i]与s2[j+1]才有可能会有交集。
根据以上分析给出实现代码如下:
func getIntersection2(l1, l2[]*MySet)[]*MySet{
result:=make([]*MySet, 0)
fori, j:=0, 0; i<len(l1)&&j<len(l2); {
s1:=l1[i]
s2:=l2[j]
if s1.Min<s2.Min{
if s1.Max<s2.Min{
i++
}elseif s1.Max<=s2.Max{
result=append(result, &MySet{s2.Min, s1.Max})
i++
}else{
result=append(result, &MySet{s2.Min, s2.Max})
j++
}
}elseif s2.Min<=s2.Max{
if s1.Max<=s2.Max{
result=append(result, &MySet{s1.Min, s1.Max})
i++
}else{
result=append(result, &MySet{s1.Min, s2.Max})
j++
}
}else{
j++
}
}
return result
}
算法性能分析: 这种方法的时间复杂度为O(n1+n2),其中n1、n2分别为两个集合的大小。