我有一份道路列表,每条道路都有一个“起点”和一个“终点”。我的目标是找到每条道路的“下一条”道路。如果一条道路的起点或终点恰好落在另一条道路的起点或终点上,则该道路是另一条道路的“下一条”道路。例如:
道路A:起点为(0,0),终点为(2,0) 道路B:起点为(2,0),终点为(5,0) 道路C:起点为(2,0),终点为(4,2)
因此,道路Next将是:
A NEXT { B , C } B NEXT { A } C NEXT { A }
我的当前算法通过将每条道路的起点与另一条道路的起点和终点进行比较,以O(n^2)的时间复杂度实现。如何使这个过程更快?我认为对道路进行排序可能有效,但我不确定。请告诉我您的想法!
注意:那些建议使用HashMap的人,您的解决方案仍然是O(N^2)。
道路A:起点为(0,0),终点为(2,0) 道路B:起点为(2,0),终点为(5,0) 道路C:起点为(2,0),终点为(4,2)
因此,道路Next将是:
A NEXT { B , C } B NEXT { A } C NEXT { A }
我的当前算法通过将每条道路的起点与另一条道路的起点和终点进行比较,以O(n^2)的时间复杂度实现。如何使这个过程更快?我认为对道路进行排序可能有效,但我不确定。请告诉我您的想法!
注意:那些建议使用HashMap的人,您的解决方案仍然是O(N^2)。