gpt4 book ai didi

algorithm - 对路口列表进行排序

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:36:44 27 4
gpt4 key购买 nike

我有一个对象

class Junction {
private String name;
private String previous;
private String next;
}

现在这些路口具有以下格式

Junction[name="T1H", previous="T0F", next="T345"]
Junction[name="K109", previous="TRH", next="JHD"]
Junction[name="LM89", previous="T1H", next="D679"]
Junction[name="TRH", previous="LM89", next="T345"]

上面的命令是这样的:

T1H->LM89->TRH->K109

但是如果我有一个无序列表,我该如何排序呢?什么是 java 中最好的算法来做到这一点。快速排序不会起作用,因为枢轴和更高和更低的概念并不真正适用。你无法计算出是否有更高的东西,因为连接点都是相连的。

冒泡排序似乎是合乎逻辑的。

有什么想法吗?

最佳答案

您可以使用散列映射来存储每个结点的后继者,使用那些结点 previous 属性。使用 Nonenull 或任何其他特殊值(如果“上一个”结点不在列表中)。这假定所有路口都是直接后继路口或某个其他路口,并且没有两个路口具有相同的“前一个”路口。对于 n 个结点,复杂度将为 O(n)。

from collections import namedtuple
Junction = namedtuple("Junction", "name previous next")
junctions = [
Junction(name="T1H", previous="T0F", next="T345"),
Junction(name="K109", previous="TRH", next="JHD"),
Junction(name="LM89", previous="T1H", next="D679"),
Junction(name="TRH", previous="LM89", next="T345")
]

d = {j.name: j for j in junctions} # map names to junctions
succ = {j: None for j in junctions} # map previous to successor
for j in junctions:
p = d.get(j.previous, None)
succ[p] = j

然后,从 None 的后继结点开始,迭代所有结点:

j = succ[None]
while j:
print(j)
j = succ[j]

输出:

Junction(name='T1H', previous='T0F', next='T345')
Junction(name='LM89', previous='T1H', next='D679')
Junction(name='TRH', previous='LM89', next='T345')
Junction(name='K109', previous='TRH', next='JHD')

(这里使用 Python,因为您没有专门要求 Java 解决方案,但当然同样可以用 Java 轻松完成。)

关于algorithm - 对路口列表进行排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56565390/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com