求无需排序、空间复杂度O(1)的图中点相交检测更优算法

问题背景 #

我有一组代表图上X、Y坐标的点列表，所有点均始于(0,0)。示例如下：

• 有效路径：[(0,0),(0,1),(0,2),(1,2),(2,2)]
• 无效路径：[(0,0),(0,1),(0,2),(1,2),(2,2),(2,1),(1,1),(0,1)]（因点(0,1)重复出现，路径自交）

当前实现方法 #

我当前采用排序后遍历检测重复的方法，时间复杂度为O(nlogn)，代码如下：

def is_intersect(points ):
    # points  [(0,0)...]
    points.sort()
    for m,u in zip(points,points[1:]):
        if m==u:
            return True
    return False 

提问 #

是否存在比上述算法更优的点相交检测方法，且要求空间复杂度为O(1)（不使用额外集合或哈希集合）？

回答 #

如果要求严格的O(1)额外空间（不修改输入数据、不依赖坐标范围等特殊前提），不存在时间复杂度优于O(nlogn)的算法，原因如下：

1. 问题本质是检测列表中的重复元素，在比较计算模型下，这类问题的时间复杂度下界就是O(nlogn)——这和排序的复杂度下界一致，因为检测重复的难度并不低于排序（排序后可线性遍历完成检测）。

2. 若要达到O(n)时间复杂度，通常需要借助哈希集合记录已出现的点，但这会产生O(n)的额外空间，不符合你的要求。

3. 如果允许修改输入列表，你可以尝试在遍历过程中用特殊值标记已访问的点，再逐个检查后续点是否与之前标记的点重复，但这种方法的时间复杂度为O(n²)，比当前的O(nlogn)算法效率更低，没有实际优势。

4. 仅当点的坐标存在明确的范围限制（比如所有坐标值都在0到k之间，k为较小常数）时，才有可能通过原地计数的方式实现O(n)时间，但这种方法依赖特定场景，不具备通用性。

综上，你当前的排序后检测重复的方法，已经是严格O(1)额外空间下的最优解法。

内容的提问来源于stack exchange，提问作者pylos