Hashing的路径重建？

Question

我一直在试图找出如何找到一个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中的算法(其他有效的解决方案非常受欢迎,因为我对这种类型的问题解决感兴趣)或者从数据结构的角度更一般地理解它.

Answer 1

下面是在 Java 中使用 HashMap 的简单实现：

    String[][] paths = {
        {"P", "B"}, 
        {"B", "M"},
        {"O", "P"},
        {"M", "Z"},
    };

    // create a single hash map, mapping start->end
    HashMap<String, String> end = new HashMap<>();

    for(int i = 0; i < paths.length; i++)
    {
        end.put(paths[i][0], paths[i][1]);
    }

    // find if a cycle exists
    String origin = null;
    for (String key : end.keySet()) {
        if(!end.containsValue(key))
        {
            origin = key;
            break;
        }
    }

    if(origin == null)
    {
        System.out.println("cycle exists");
        return;  // no origin found, cycle exists
    }

    // iterate over hash map:
    int count = 0;
    while(true)
    {
        if(!end.containsKey(origin))
            break;
        String next = end.get(origin);
        System.out.println(origin + " " + next);
        origin = next;
        if(++count > paths.length)
        {
            System.out.println("cycle exists");
            break;
        }
    }

end存储给定起点（键）的终点（值）。

如果一个点作为起点而不是终点存在，那么它将是 中的键end，但不是 中的值end。因此，迭代 keySetend并检查是否end包含每个键作为值将找到一个起源。如果没有这样的起源，那么就有一个循环。然而，这不足以确定是否存在循环，因为即使有原点也可能存在循环。考虑这个集合：

P B 
B M
O P
M Z
Z M

有一个唯一的原点 (O)，但也有一个循环 M -> Z -> M。要检测到这一点，您可以遍历集合并跟踪您已经访问过的点，或者更简单地，您可以遍历集合并如果您最终访问的点多于输入的长度，则一定存在循环。

要遍历集合，请将字符串设置为原点。然后继续查找end给定中的值origin作为键，并打印出键、值对(origin, end.get(origin))作为开始、结束。然后将 end.get(origin) 设置为新的原点。当在当前原点的结束 HashMap 中找不到值时，循环终止。

如果列表中存在重复的开始或结束位置，则该算法将失败，例如：

P B 
B M
O P
M Z
B Z

从问题中尚不清楚您是否必须处理此案。