小编fre*_*rei的帖子

我一直在试图找出如何找到一个O(n)时间复杂度算法来解决Java中的以下问题:

我们给出了一个带有起点和终点的输入对,我们必须构造一个路径,使得一个输入的开始与另一个输入的结束匹配(在这种情况下,按字母顺序排列)

EX:如果我有一份清单

PB
BM
OP
MZ

其中PB或BM是成对的,P是起点,B是结束

我应该创建输出

OP
PB
BM
MZ

当然,我想检查周期 - 在这种情况下,我只会报告是否存在周期.

我第一次尝试这样做时,我使用了一个O(N ^ 2)的交换算法,基本上交换了两个条目,如果有匹配并向下移动列表.有一个绝对更快的方法来做到这一点,我直觉地知道如何做到这一点,但我想知道是否有人可以清除它.

基本上,我假设您需要制作某种哈希/键类型的结构,您可以通过键引用对象本身的值.

例如,您将保留两个集合,一个是开始,另一个是结束.您可以获取每个输入并创建一个具有开始和结束字段的对象,然后将所有开始和结束添加到两个数组中.然后你必须找到每个开始的基本结束[start]并在找到它们之后将它们各自的对象添加到列表中.

我唯一的问题是,我无法弄清楚如何使用哈希表或类似的数据结构在Java中实现它.我是否必须将开始和结束添加到单独的哈希表中,然后将起点用作查找键？

看看在github上的python中解决它的人的伪代码:

for inputs
    parse input 
    add parse[1] to starts, add parse[2] to ends

for starts
    find origin (a start not in ends) <--requires hash?

if no origin
    cycle exists

for inputs
    find ends[origin] <--requires hash?
    origin = ends[origin] <-- so we can find the next one

想知道是否有人可以帮助我将其转换为Java中的算法(其他有效的解决方案非常受欢迎,因为我对这种类型的问题解决感兴趣)或者从数据结构的角度更一般地理解它.