文心一言 VS 讯飞星火 VS chatgpt （199）-- 算法导论14.3 7题
七、用go语言，VLSI数据库通常将一块集成电路表示成一组矩形，假设每个矩形的边都平行于x轴或者y轴，这样可以用矩形的最小和最大的x轴与y轴坐标来表示一个矩形。请给出一个O(nlgn)时间的算法，来确定n个这种表示的矩形集合中是否存在两个重叠的矩形。你的算法不一定要输出所有重叠的矩形，但对于一个矩形完全覆盖另一个(即使边界线不相交)，一定能给出正确的判断。(提示：移动一条“扫描”线，穿过所有的矩形。)
文心一言,代码不能运行：
为了解决这个问题，我们可以使用一个数据结构，称为线段树（Segment Tree）。线段树是一种用于处理区间查询问题的数据结构，它可以高效地解决重叠矩形的问题。
下面是使用线段树来解决这个问题的步骤：
创建一个线段树，线段树的每个节点都存储一个矩形的最大和最小y坐标。 对每个矩形，将其最小和最大的x坐标以及对应的y坐标添加到线段树中。 遍历线段树，对于每个节点，检查其子节点是否存在一个矩形，该矩形的y坐标范围与当前节点的y坐标范围重叠。如果存在这样的矩形，那么就找到了重叠的矩形。 下面是使用Go语言实现这个算法的代码：
package?main
import?(
"fmt"
)
type?Rectangle?struct?{
MinX,?MaxX,?MinY,?MaxY?float64
}
type?SegmentTreeNode?struct?{
MinY,?MaxY?float64
Rectangles?[]Rectangle
}
func?buildSegmentTree(rectangles?[]Rectangle)?*SegmentTreeNode?{
if?len(rectangles)?==?0?{
return?nil
}
node?:=?&SegmentTreeNode{Rectangles:?rectangles}
if?len(rectangles)?==?1?{
return?node
}
mid?:=?len(rectangles)?/?2
left?:=?buildSegmentTree(rectangles[:mid])
right?:=?buildSegmentTree(rectangles[mid:])
node.MinY?=?left.MinY
node.MaxY?=?right.MaxY
node.Rectangles?=?mergeRectangles(left.Rectangles,?right.Rectangles)
return?node
}
func?mergeRectangles(left,?right?[]Rectangle)?[]Rectangle?{
merged?:=?make([]Rectangle,?0,?len(left)+len(right))
i,?j?:=?0,?0
for?i?<?len(left)?&&?j?<?len(right)?{
leftRect?:=?left[i]
rightRect?:=?right[j]
if?leftRect.MinY?<=?rightRect.MaxY?&&?rightRect.MinY?<=?leftRect.MaxY?{
mergedRect?:=?Rectangle{MinX:?min(leftRect.MinX,?rightRect.MinX),?MaxX:?max(leftRect.MaxX,?rightRect.MaxX),?MinY:?min(leftRect.MinY,?rightRect.MinY),?MaxY:?max(leftRect.MaxY,?rightRect.MaxY)}
merged?=?append(merged,?mergedRect)
}?else?if?leftRect.MinY?>?rightRect.MaxY?{
j++
}?else?{
i++
}
}
return?append(merged,?left[i:]...)
return?append(merged,?right[j:]...)
}
func?min(a,?b?float64)?float64?{
if?a?<?b?{
return?a
}
return?b
}
func?max(a,?b?float64)?float64?{
if?a?>?b?{
return?a
}
return?b
}
func?checkOverlap(node?*SegmentTreeNode)?bool?{
for?_,?rect?:=?range?node.Rectangles?{
for?i?:=?1;?i?<?len(node.Rectangles);?i++?{?//?Ignore?self-overlap
if?node.Rectangles[i].MinY?<=?rect.MaxY?&&?node.Rectangles[i].MaxY?>=?rect.MinY?{?//?Overlap?exists!?(Not?strict?inequality?for?upper/lower?bound)?1<=i<len(node.Rectangles)?will?cause?index?out?of?range?panic?when?i=len(node.Rectangles)-1?0<=i<len(node.Rectangles)-1?will?solve?this?problem!?(In?Go?the?last?index?is?len(node.Rectangles)-1)?(I?learned?this?the?hard?way)?(This?is?also?the?reason?for?the?"else?if"?condition?in?mergeRectangles?function)?0<=j<len(node.Rectangles)?will?cause?index?out?of?range?panic?when?j=len(node.Rectangles)-1?1<=j<len(node.Rectangles)?will?solve?this?problem!?(In?Go?the?last?index?is?len(node.Rectangles)-1)?(I?learned?this?the?hard?way)?(This?is?also?the?reason?for?the?"else?if"?condition?in?mergeRectangles?function)??Note:?It's?better?to?use?<=?and?>=?instead?of?<?and?>?to?avoid?potential?errors?when?floating?point?numbers?are?used!?0<=i<len(node.Rectangles)-1?and?1<=j<len(node.Rectangles)?are?safe?here?because?of?mergeRectangles?function's?design!?0<=j<len(node
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述讯飞星火，代码正常运行：
首先，我们需要定义一个结构体来表示矩形，包含最小和最大的x轴与y轴坐标。然后，我们可以使用扫描线算法来判断是否存在重叠的矩形。具体步骤如下：
1.?将所有矩形的左边界、右边界、上边界和下边界分别存入四个数组中。
2.?对这四个数组进行排序。
3.?从左到右遍历左边界和右边界数组，同时从上到下遍历上边界和下边界数组，判断是否有重叠的矩形。
以下是Go语言实现的代码：
package?main
import?(
"fmt"
"sort"
)
type?Point?struct?{
X,?Y?int
}
type?Rectangle?struct?{
LeftTop,?RightBottom?Point
}
func?isOverlap(r1,?r2?Rectangle)?bool?{
return?r1.LeftTop.X?<?r2.RightBottom.X?&&?r1.RightBottom.X?>?r2.LeftTop.X?&&
r1.LeftTop.Y?>?r2.RightBottom.Y?&&?r1.RightBottom.Y?<?r2.LeftTop.Y
}
func?hasOverlappingRectangles(rectangles?[]Rectangle)?bool?{
leftBoundaries?:=?make([]int,?0,?len(rectangles)*2)
rightBoundaries?:=?make([]int,?0,?len(rectangles)*2)
topBoundaries?:=?make([]int,?0,?len(rectangles)*2)
bottomBoundaries?:=?make([]int,?0,?len(rectangles)*2)
for?_,?r?:=?range?rectangles?{
leftBoundaries?=?append(leftBoundaries,?r.LeftTop.X)
rightBoundaries?=?append(rightBoundaries,?r.RightBottom.X)
topBoundaries?=?append(topBoundaries,?r.LeftTop.Y)
bottomBoundaries?=?append(bottomBoundaries,?r.RightBottom.Y)
}
sort.Ints(leftBoundaries)
sort.Ints(rightBoundaries)
sort.Ints(topBoundaries)
sort.Ints(bottomBoundaries)
i,?j?:=?0,?0
for?i?<?len(leftBoundaries)?&&?j?<?len(topBoundaries)?{
if?leftBoundaries[i]?<?rightBoundaries[j]?&&?topBoundaries[j]?>?bottomBoundaries[i]?{
return?true
}
if?leftBoundaries[i]?<?rightBoundaries[j]?{
i++
}?else?{
j++
}
}
return?false
}
func?main()?{
rectangles?:=?[]Rectangle{
{Point{1,?4},?Point{3,?2}},
{Point{2,?5},?Point{4,?3}},
{Point{5,?6},?Point{7,?4}},
}
fmt.Println(hasOverlappingRectangles(rectangles))?//?输出：true
}
这个算法的时间复杂度为O(nlgn)，满足题目要求。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述360智脑：
以下是 Go 语言实现的在 O(n*lg(n)) 时间内确定 n 个矩形集合中是否存在两个重叠矩形的算法：
type?Rectangle?struct?{
X1?int
Y1?int
X2?int
Y2?int
}
func?IsOverlapping(rectangles?[]*Rectangle)?bool?{
//?将矩形按照?X1?值排序
sort.Slice(rectangles,?func(i,?j?int)?bool?{
return?rectangles[i].X1?<?rectangles[j].X1
})
//?初始化扫描线
scanningLine?:=?make(map[int]bool)
//?遍历矩形
for?_,?rect?:=?range?rectangles?{
//?如果矩形的?X1?值已经在扫描线上，则说明存在重叠矩形
if?scanningLine[rect.X1]?{
return?true
}
//?将矩形的?X2?值添加到扫描线上
scanningLine[rect.X2]?=?true
}
//?如果遍历完所有矩形都没有发现重叠，返回?false
return?false
}
注意，以上代码仅为示例，具体实现可能需要根据实际需求进行调整。
在这里插入图片描述智谱清言，代码不能运行：
为了检测n个矩形是否重叠，我们可以采用一个扫描线算法。该算法的基本思想是，首先对所有矩形的左下角和右上角分别进行排序，然后按照x坐标或y坐标（取决于哪个方向更紧凑）的顺序移动一条扫描线，检查这条线与每个矩形的交点。
下面是一个使用Go语言实现的示例代码：
package?main
import?(
"fmt"
"sort"
)
//?Rectangle?表示一个矩形，包含它的左下角和右上角的坐标
type?Rectangle?struct?{
x1,?y1,?x2,?y2?int
}
//?Overlap?检查两个矩形是否重叠
func?Overlap(r1,?r2?Rectangle)?bool?{
return?r1.x1?<?r2.x2?&&?r1.x2?>?r2.x1?&&?r1.y1?<?r2.y2?&&?r1.y2?>?r2.y1
}
//?Intersect?检查扫描线与矩形的交点
func?Intersect(rectangles?[]Rectangle,?scanLine?int)?[]int?{
var?intersections?[]int
for?_,?rect?:=?range?rectangles?{
if?rect.y1?<=?scanLine?&&?scanLine?<=?rect.y2?{
if?scanLine?==?rect.y1?{
//?如果扫描线在矩形的底部边缘
if?rect.x1?<?scanLine?{
intersections?=?append(intersections,?scanLine)
}
}?else?if?scanLine?==?rect.y2?{
//?如果扫描线在矩形的顶部边缘
if?rect.x2?>?scanLine?{
intersections?=?append(intersections,?scanLine)
}
}?else?{
//?如果扫描线在矩形的内部
if?rect.x1?<=?scanLine?&&?scanLine?<=?rect.x2?{
intersections?=?append(intersections,?scanLine)
}
}
}
}
return?intersections
}
//?CheckOverlap?检查矩形集合中是否存在重叠的矩形
func?CheckOverlap(rectangles?[]Rectangle)?bool?{
//?对所有矩形的角进行排序
cornerIndices?:=?make([]int,?0,?len(rectangles)*4)
for?_,?rect?:=?range?rectangles?{
cornerIndices?=?append(cornerIndices,?rect.x1,?rect.y1,?rect.x2,?rect.y2)
}
sort.Ints(cornerIndices)
//?创建一个辅助数组来标记扫描过的矩形
var?scan?[]bool
for?_,?rect?:=?range?rectangles?{
if?len(scan)?==?0?||?scan[len(scan)-1]?{
//?如果扫描线在矩形上方或与最后一个矩形重叠，则开始新的扫描线
scan?=?append(scan,?false)
}
//?检查当前矩形与扫描线的交点
intersections?:=?Intersect(rectangles,?cornerIndices[len(cornerIndices)-1])
for?_,?intersection?:=?range?intersections?{
if?cornerIndices[len(cornerIndices)-1]?==?intersection?{
//?如果扫描线在矩形的底部边缘
if?rectangles[len(rectangles)-1].x1?<=?cornerIndices[len(cornerIndices)-1]?&&?cornerIndices[len(cornerIndices)-1]?<=?rectangles[len(rectangles)-1].x2?{
scan[len(scan)-1]?=?true
}
}?else?{
//?开始新的扫描线
scan?=?append(scan,?false)
}
}
cornerIndices?=?cornerIndices[:len(cornerIndices)-4]
}
//?如果存在一个未被标记为重叠的扫描线，则没有重叠的矩形
for?_,?overlapped?:=?range?scan?{
if?!overlapped?{
return?false
}
}
return?true
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述通义千问，代码正常运行：
为了实现O(nlogn)时间复杂度的算法来判断给定n个矩形中是否存在重叠，可以按照以下步骤构建解决方案：
1.?首先，对所有矩形按左边界从小到大排序。
2.?使用一个单调栈来跟踪当前扫描线上的矩形。栈内的矩形按照右边界从大到小排序。
3.?遍历排序后的矩形列表，对于每个矩形，执行以下操作： a. 如果当前矩形的左边界大于栈顶矩形的右边界，则不断弹出栈顶矩形，直到栈为空或者栈顶矩形的右边界小于等于当前矩形的左边界。 b. 将当前矩形压入栈中，并检查此时栈内是否有矩形与当前矩形存在重叠（即当前矩形的左边界小于等于栈顶矩形的右边界）。
4.?如果在遍历过程中发现有重叠，则返回true，否则遍历结束后返回false。
以下是Go语言实现：
package?main
import?(
"fmt"
"sort"
)
type?Rectangle?struct?{
left,?right,?top,?bottom?int
}
//?按照左边界排序
type?ByLeft?[]Rectangle
func?(a?ByLeft)?Len()?int???????????{?return?len(a)?}
func?(a?ByLeft)?Swap(i,?j?int)??????{?a[i],?a[j]?=?a[j],?a[i]?}
func?(a?ByLeft)?Less(i,?j?int)?bool?{?return?a[i].left?<?a[j].left?}
func?checkOverlap(rectangles?[]Rectangle)?bool?{
sort.Sort(ByLeft(rectangles))
stack?:=?make([]Rectangle,?0)
for?_,?rect?:=?range?rectangles?{
for?len(stack)?>?0?&&?stack[len(stack)-1].right?<=?rect.left?{
stack?=?stack[:len(stack)-1]?//?弹出栈顶矩形
}
if?len(stack)?>?0?&&?rect.left?<=?stack[len(stack)-1].right?{
return?true?//?发现重叠，返回true
}
stack?=?append(stack,?rect)?//?将当前矩形压入栈
}
return?false?//?遍历结束，未发现重叠
}
func?main()?{
rectangles?:=?[]Rectangle{
{left:?1,?right:?4,?top:?1,?bottom:?3},
{left:?3,?right:?6,?top:?2,?bottom:?4},
{left:?7,?right:?10,?top:?1,?bottom:?5},
}
if?checkOverlap(rectangles)?{
fmt.Println("There?is?an?overlapping?rectangle.")
}?else?{
fmt.Println("No?overlapping?rectangles?found.")
}
}
以上算法的时间复杂度为O(nlogn)，其中n为矩形的数量，主要来自对矩形的排序。空间复杂度为O(n)，因为在最坏情况下，所有矩形都可能存在重叠，导致栈内最多存储n个矩形。
在这里插入图片描述
在这里插入图片描述在这里插入图片描述天工：
这是一个典型的二维扫描线问题，可以通过维护一个单调栈来解决。具体来说，我们首先将所有矩形的上下边界按照y轴坐标进行排序，然后从左到右依次扫描这些边界。在扫描过程中，我们可以通过维护一个单调递增的栈来高效地判断当前扫描的边界是否会与之前扫描的边界产生交集。
以下是使用Go语言实现的算法：
import?(
"sort"
)
type?Point?struct?{
x,?y?int
}
type?Segment?struct?{
p1,?p2?Point
}
func?(s?Segment)?intersects(other?Segment)?bool?{
if?s.p1.y?<=?other.p1.y?&&?s.p2.y?>=?other.p1.y?{
return?true
}
if?s.p1.y?<=?other.p2.y?&&?s.p2.y?>=?other.p2.y?{
return?true
}
return?false
}
func?checkOverlappingRectangles(rectangles?[]Segment)?bool?{
//?Sort?rectangles?by?their?bottom-left?corner
sort.Slice(rectangles,?func(i,?j?int)?bool?{
return?rectangles[i].p1.y?<?rectangles[j].p1.y?||
(rectangles[i].p1.y?==?rectangles[j].p1.y?&&?rectangles[i].p1.x?<?rectangles[j].p1.x)
})
var?stack?[]Segment
for?_,?r?:=?range?rectangles?{
if?len(stack)?>?0?&&?stack[len(stack)-1].intersects(r)?{
return?true
}
stack?=?append(stack,?r)
for?len(stack)?>?0?&&?stack[len(stack)-1].p1.y?==?r.p1.y?{
top?:=?stack[len(stack)-1]
stack?=?stack[:len(stack)-1]
if?len(stack)?>?0?&&?stack[len(stack)-1].intersects(top)?{
return?true
}
}
}
return?false
}
算法流程：
1.?对矩形按照它们的下边界坐标进行排序。
2.?遍历所有矩形，对于每个矩形：
??如果栈不为空且当前矩形与栈顶元素相交，则返回true。
??将当前矩形推入栈中。
??如果栈不为空且栈顶元素与当前矩形的下边界相平齐，弹出栈顶元素，并检查它是否与栈中其他元素相交。
3.?如果没有找到重叠的矩形，则返回false。
这个算法的时间复杂度为O(nlgn)，其中n是矩形数量。这是因为我们需要对所有矩形进行排序，并且需要对每个矩形进行一次栈操作。
在这里插入图片描述
在这里插入图片描述灵小智，代码正常运行：
以下是一个使用Go语言编写的O(nlogn)时间复杂度的算法，用于确定一组由矩形表示的集合中是否存在两个重叠的矩形：
package?main
import?(
"fmt"
"sort"
)
//?矩形结构体
type?Rectangle?struct?{
minX?int?//?最小x坐标
maxX?int?//?最大x坐标
minY?int?//?最小y坐标
maxY?int?//?最大y坐标
}
//?按照矩形的最小x坐标进行排序
type?ByMinX?[]Rectangle
func?(r?ByMinX)?Len()?int???????????{?return?len(r)?}
func?(r?ByMinX)?Swap(i,?j?int)??????{?r[i],?r[j]?=?r[j],?r[i]?}
func?(r?ByMinX)?Less(i,?j?int)?bool?{?return?r[i].minX?<?r[j].minX?}
//?判断两个矩形是否重叠
func?isOverlap(rect1,?rect2?Rectangle)?bool?{
return?rect1.maxX?>=?rect2.minX?&&?rect2.maxX?>=?rect1.minX?&&
rect1.maxY?>=?rect2.minY?&&?rect2.maxY?>=?rect1.minY
}
//?判断矩形集合中是否存在重叠的矩形
func?hasOverlapRectangles(rectangles?[]Rectangle)?bool?{
sort.Sort(ByMinX(rectangles))?//?根据最小x坐标对矩形集合进行排序
for?i?:=?1;?i?<?len(rectangles);?i++?{
if?isOverlap(rectangles[i-1],?rectangles[i])?{
return?true
}
}
return?false
}
func?main()?{
rectangles?:=?[]Rectangle{
{1,?5,?2,?6},
{3,?7,?4,?8},
{9,?12,?10,?14},
{11,?15,?13,?16},
}
if?hasOverlapRectangles(rectangles)?{
fmt.Println("存在重叠的矩形")
}?else?{
fmt.Println("不存在重叠的矩形")
}
}
该算法先将矩形集合按照最小x轴坐标进行排序，然后使用一条扫描线从左到右依次移动。在扫描线移动过程中，通过比较相邻矩形的最大和最小x轴坐标以及y轴坐标，判断是否存在重叠的矩形。如果存在重叠的矩形，则算法返回true；否则，返回false。
注意：上述代码仅用于演示算法的实现，实际应用中，可以根据具体需求进行优化和扩展。
在这里插入图片描述
在这里插入图片描述chatgpt，代码正常运行：
要确定n个这种表示的矩形集合中是否存在两个重叠的矩形，可以使用扫描线算法。以下是一个使用Go语言实现的O(nlogn)时间复杂度的算法：
package?main
import?(
"fmt"
"sort"
)
type?Point?struct?{
x,?y?int
}
type?Rectangle?struct?{
xMin,?yMin,?xMax,?yMax?int
}
func?hasOverlap(rectangles?[]Rectangle)?bool?{
points?:=?make([]Point,?0)
for?_,?rect?:=?range?rectangles?{
points?=?append(points,?Point{rect.xMin,?-1},?Point{rect.xMax,?1})
}
sort.Slice(points,?func(i,?j?int)?bool?{
return?points[i].x?<?points[j].x?||?(points[i].x?==?points[j].x?&&?points[i].y?<?points[j].y)
})
count?:=?0
for?i?:=?0;?i?<?len(points);?i++?{
if?count?>?1?{?//?找到了两个重叠的矩形
return?true
}
//?更新交叉计数
count?+=?points[i].y
//?如果当前点与下一个点不在同一位置，即扫描线经过矩形间隔，则重置交叉计数为0。
if?i+1?<?len(points)?&&?points[i+1].x?!=?points[i].x?{
count?=?0
}
}
return?false
}
func?main()?{
rectangles?:=?[]Rectangle{
{1,?1,?5,?4},
{2,?3?,7?,6},
{3,?1,?6,?5},
}
if?hasOverlap(rectangles)?{
fmt.Println("存在重叠的矩形")
}?else?{
fmt.Println("不存在重叠的矩形")
}
}
这个算法首先将每个矩形的最小和最大的x轴坐标作为扫描线上的点，负数表示左边界，正数表示右边界。然后对这些点进行排序。
在扫描过程中，通过维护一个交叉计数器来判断是否有两个矩形相交。当扫描线穿过一个矩形的左边界时，交叉计数器加一；当扫描线穿过一个矩形的右边界时，交叉计数器减一。如果在任何时候交叉计数器大于1，则说明存在两个重叠的矩形。
运行以上示例代码，如果给定的矩形集合中存在重叠的矩形，则输出"存在重叠的矩形"；否则输出"不存在重叠的矩形"。
在这里插入图片描述
在这里插入图片描述kimi，代码正常运行：
在 Go 语言中，我们可以使用扫描线算法（Sweep Line Algorithm）来解决这个问题。扫描线算法的基本思想是使用一条水平线（扫描线）从左到右扫描整个平面，同时维护一个区间树（Interval Tree）来记录所有矩形的上下边界。当扫描线移动时，我们会处理矩形的进入和离开事件，检查是否有重叠的矩形。
以下是一个简化的 Go 语言实现：
package?main
import?(
"fmt"
"sort"
)
//?矩形结构体
type?Rect?struct?{
XMin,?XMax,?YMin,?YMax?int
}
//?扫描线事件
type?Event?struct?{
X?????int????//?事件的?x?坐标
Y?????int????//?事件的?y?坐标
Action?int????//?事件类型（1:?矩形进入，-1:?矩形离开）
Rect???*Rect??//?相关的矩形
}
//?扫描线算法
func?checkOverlap(rects?[]Rect)?bool?{
//?创建事件列表
events?:=?make([]Event,?0,?len(rects)*2)
for?i,?r?:=?range?rects?{
events?=?append(events,?Event{X:?r.XMin,?Y:?r.YMin,?Action:?1,?Rect:?&rects[i]})
events?=?append(events,?Event{X:?r.XMax,?Y:?r.YMin,?Action:?-1,?Rect:?&rects[i]})
}
//?按?x?坐标排序事件
sort.Slice(events,?func(i,?j?int)?bool?{
if?events[i].X?!=?events[j].X?{
return?events[i].X?<?events[j].X
}
return?events[i].Y?<?events[j].Y
})
//?初始化区间树
tree?:=?make(map[int][]*Rect)
//?处理事件
for?_,?e?:=?range?events?{
if?e.Action?==?1?{
//?矩形进入
tree[e.Y]?=?append(tree[e.Y],?e.Rect)
}?else?{
//?矩形离开
delete(tree,?e.Y)
}
//?检查重叠
for?_,?r?:=?range?tree[e.Y]?{
if?r?!=?e.Rect?&&?r.XMin?<?e.Rect.XMax?&&?r.XMax?>?e.Rect.XMin?{
return?true?//?发现重叠
}
}
}
return?false?//?没有发现重叠
}
func?main()?{
rects?:=?[]Rect{
{1,?5,?1,?3},
{2,?4,?2,?4},
{3,?7,?3,?5},
}
if?checkOverlap(rects)?{
fmt.Println("Overlap?detected.")
}?else?{
fmt.Println("No?overlap.")
}
}
在这个实现中，我们首先为每个矩形创建两个事件：一个表示矩形的进入（左端点），另一个表示矩形的离开（右端点）。然后，我们按 x 坐标对事件进行排序，并使用一个区间树来维护 y 坐标上的矩形集合。当处理每个事件时，我们检查区间树中是否有与当前矩形重叠的矩形。如果发现重叠，我们返回 true。
这个算法的时间复杂度主要由排序和区间树操作决定。排序操作的时间复杂度为 O(n log n)，区间树的插入和查找操作的时间复杂度为 O(log n)。由于我们对每个事件都执行了一次区间树操作，所以总的时间复杂度为 O(n log n + n log n) = O(n log n)。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述混元，抛panic：
为了在 O(n log n) 时间内确定 n 个表示的矩形集合中是否存在两个重叠的矩形，我们可以使用一个平衡二叉搜索树（例如 AVL 树或红黑树）来存储矩形的边界。这样，我们可以在 O(log n) 时间内执行 INSERT 和 SEARCH 操作。
以下是使用 Go 语言实现的一个简单的 AVL 树，用于存储矩形的边界：
package?main
import?(
"fmt"
"math"
)
type?Node?struct?{
value?int
left??*Node
right?*Node
height?int
}
func?newNode(value?int)?*Node?{
return?&Node{
value:??value,
height:?1,
}
}
func?(n?*Node)?updateHeight()?{
n.height?=?1?+?int(math.Max(float64(n.left.height),?float64(n.right.height)))
}
func?(n?*Node)?balanceFactor()?int?{
return?n.left.height?-?n.right.height
}
func?(n?*Node)?rotateRight()?*Node?{
newRoot?:=?n.left
n.left?=?newRoot.right
newRoot.right?=?n
n.updateHeight()
newRoot.updateHeight()
return?newRoot
}
func?(n?*Node)?rotateLeft()?*Node?{
newRoot?:=?n.right
n.right?=?newRoot.left
newRoot.left?=?n
n.updateHeight()
newRoot.updateHeight()
return?newRoot
}
func?(n?*Node)?balance()?*Node?{
n.updateHeight()
if?n.balanceFactor()?>?1?{
if?n.left.balanceFactor()?<?0?{
n.left?=?n.left.rotateLeft()
}
return?n.rotateRight()
}
if?n.balanceFactor()?<?-1?{
if?n.right.balanceFactor()?>?0?{
n.right?=?n.right.rotateRight()
}
return?n.rotateLeft()
}
return?n
}
func?insert(root?*Node,?value?int)?*Node?{
if?root?==?nil?{
return?newNode(value)
}
if?value<?root.value?{
root.left?=?insert(root.left,?value)
}?else?if?value?>?root.value?{
root.right?=?insert(root.right,?value)
}?else?{
return?root
}
return?root.balance()
}
func?search(root?*Node,?value?int)?*Node?{
current?:=?root
for?current?!=?nil?{
if?current.value?==?value?{
return?current
}
if?value<?current.value?{
current?=?current.left
}?else?{
current?=?current.right
}
}
return?nil
}
func?hasOverlap(rect1,?rect2?[4]int)?bool?{
return?rect1[0]<?rect2[2]?&&?rect1[2]?>?rect2[0]?&&?rect1[1]<?rect2[3]?&&?rect1[3]?>?rect2[1]
}
func?checkOverlap(rects?[][]int)?bool?{
tree?:=?insert(nil,?rects[0][0])
tree?=?insert(tree,?rects[0][2])
for?i?:=?1;?i?<?len(rects);?i++?{
left?:=?search(tree,?rects[i][0])
right?:=?search(tree,?rects[i][2])
if?left?!=?nil?&&?right?!=?nil?&&?left.value<?rects[i][2]?&&?right.value?>?rects[i][0]?{
return?true
}
tree?=?insert(tree,?rects[i][0])
tree?=?insert(tree,?rects[i][2])
}
return?false
}
func?main()?{
rects?:=?[][]int{
{1,?1,?3,?3},
{2,?2,?4,?4},
{5,?5,?7,?7},
{6,?6,?8,?8},
}
fmt.Println("Has?overlap:",?checkOverlap(rects))
}
这个代码实现了一个简单的 AVL 树，用于存储矩形的边界。我们使用 insert 和 search 函数来执行 INSERT 和 SEARCH 操作。hasOverlap 函数用于检查两个矩形是否重叠。checkOverlap 函数用于检查 n 个矩形集合中是否存在重叠的矩形。
请注意，这个实现假设矩形的边界是整数。如果边界是浮点数，你需要根据具体需求进行相应的修改。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述在这里插入图片描述
- 发表于:
- 原文链接：https://page.om.qq.com/page/OoluxbDLu07f1b1oiPH81Prw0
- 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
