相关疑难解决方法(0)

是否存在一个算法,给定两组,在线性时间内计算它们的交集？

我可以运行两个for循环来检查所有元素对,记录我在两个集合中找到的元素.但是,运行时间将为O(n ²).我如何在O(n)时间内完成此操作？

下午好.

我的情况:

• 在二维空间.
• 输入:一组矩形(也是重叠的矩形).
  • 矩形坐标是整数类型.
  • 矩形大小和矩形位置有任何限制(仅限整数范围).
  • 任何矩形都没有width = 0或height = 0.
• 我需要找到:包含输入点的所有矩形(带整数坐标).

问题:

• 保持矩形的有效结构是什么？
• 在这种情况下,哪种算法是有效的？
  • 什么算法只有在没有移除的情况下添加矩形才有效？

谢谢 :-).