单程飞行旅行问题

Question

您正在进行单向间接飞行旅行,其中包括数十亿 未知的大量转移.

• 你不是在同一个机场停车两次.
• 您的旅行的每个部分都有1张门票.
• 每张票都包含src和dst机场.
• 您拥有的所有门票都是随机分类的.
• 你忘了原来的出发机场(第一个src)和你的目的地(最后一个dst).

设计一个算法来重建有最低大端您的行程Ø复杂性.

---

试图解决这个问题我已经开始使用两组的对称差异,Srcs和Dsts:

1)对数组Srcs中的所有src键进行
排序2)对数组中的所有dst键进行排序Dsts
3)创建两个数组的联合集以查找非重复项 - 它们是您的第一个src和最后一个dst
4)现在,有了起点,使用二进制搜索遍历两个数组.

但我认为必须有另一种更有效的方法.

Answer 1

构造一个哈希表并将每个机场添加到哈希表中.

<key,value> = <airport, count>

如果机场是源头或目的地,机场的数量会增加.因此,对于每一个机场的数量将是2(对于DST 1 src和1)除源和你的旅行目的地,这将有计数为1.

你需要至少查看一次票.所以复杂性是O(n).

Answer 2

摘要:下面给出了单遍算法.(即,不仅是线性的,但看起来每张票恰好一次,这当然是每票参观的最佳数量).我把摘要放在一边,因为有许多看似相同的解决方案,很难发现为什么我添加了另一个.:)

实际上我在接受采访时被问到这个问题.这个概念非常简单:每张票都是一个单例列表,概念上有两个元素,src和dst.

我们使用其第一个和最后一个元素作为键在哈希表中索引每个这样的列表,因此我们可以在O(1)中找到列表在特定元素(机场)开始或结束的情况.对于每张票,当我们看到它从另一个列表结束的地方开始时,只需链接列表(O(1)).同样,如果它在另一个列表开始的地方结束,则另一个列表加入 当然,当我们链接两个列表时,我们基本上会破坏这两个列表并获得一个.(N票据链将在N-1个此类链接之后构建).

需要注意保持哈希表键完全是剩余列表的第一个和最后一个元素的不变量.

总而言之,O(N).

是的,我当场回答:)

编辑忘了添加一个重点.每个人都提到了两个哈希表,但其中一个也是诀窍,因为算法不变包括最多一个票据列表在任何一个城市开始或开始(如果有两个,我们立即加入该城市的列表,并删除该城市来自散列表).渐渐地没有区别,这种方式更简单.

编辑2同样令人感兴趣的是,与使用2个哈希表的解决方案相比,每个哈希表都有N个条目,这个解决方案使用一个哈希表,最多只有N/2个条目(如果我们按照第1,第3,第3, 5,依此类推).因此,除了更快之外,这也使用大约一半的内存.

Answer 3

构造两个哈希表(或尝试),一个键入src,另一个键入dst.随机选择一张票,并在src-hash表中查找其dst.对结果重复该过程,直到结束(最终目的地).现在在dst-keyed哈希表中查找其src.对结果重复此过程,直到您开始.

构造哈希表需要O(n),构造列表需要O(n),因此整个算法是O(n).

编辑:实际上,您只需要构建一个哈希表.假设您构造了src-keyed哈希表.随机选择一张票并像以前一样,构建通往最终目的地的列表.然后从尚未添加到列表中的故障单中选择另一个随机故障单.按照目的地,直到您点击最初开始使用的故障单.重复此过程,直到构造完整个列表.它仍然是O(n),因为最坏的情况是你以相反的顺序选择门票.

编辑:在我的算法中交换了表名.

Answer 4

它基本上是一个依赖图,其中每个票证代表一个节点,src和dst机场代表有向链接,因此使用拓扑排序来确定航班顺序.

编辑:虽然这是一张机票,你知道你实际上已经制定了行程,你可以按照UTC的出发日期和时间进行排序.

编辑2:假设每个机场都有使用三字符代码的票证,您可以使用此处描述的算法(查找三个号码仅出现一次),通过将所有机场合并在一起来确定两个独特的机场.

EDIT3:这是使用xor方法实际解决这个问题的一些C++.假设从机场到整数的独特编码(假定使用三个字母的机场代码或使用纬度和经度将整个机场位置编码为整数),整个算法如下:

首先,将所有机场代码合并在一起.这应该等于最终目的地机场XOR的初始源机场.由于我们知道初始机场和最终机场是唯一的,因此该值不应为零.由于它不为零,因此该值中至少会设置一个位.该位对应于在一个机场中设置而未在另一个机场中设置的位; 称之为指示位.

接下来,设置两个桶,每个桶都具有第一步的XORed值.现在,对于每个机票,根据是否设置了指示符位来对每个机场进行分配,并将机场代码与机箱中的值进行对比.同时跟踪每个桶有多少源机场和目的地机场到达该桶.

处理完所有票证后,选择其中一个票据.发送到该存储桶的源机场数应该大于或小于发送到该存储桶的目标机场数.如果源机场的数量小于目的地机场的数量,则意味着初始源机场(唯一的唯一源机场)被发送到另一个桶.这意味着当前存储桶中的值是初始源机场的标识符!相反,如果目的地机场的数量小于源机场的数量,则最终目的地机场被发送到另一个桶,因此当前桶是最终目的地机场的标识符!

struct ticket
{
    int src;
    int dst;
};

int get_airport_bucket_index(
    int airport_code, 
    int discriminating_bit)
{
    return (airport_code & discriminating_bit)==discriminating_bit ? 1 : 0;
}

void find_trip_endpoints(const ticket *tickets, size_t ticket_count, int *out_src, int *out_dst)
{
    int xor_residual= 0;

    for (const ticket *current_ticket= tickets, *end_ticket= tickets + ticket_count; current_ticket!=end_ticket; ++current_ticket)
    {
        xor_residual^= current_ticket->src;
        xor_residual^= current_ticket->dst;
    }

    // now xor_residual will be equal to the starting airport xor ending airport
    // since starting airport!=ending airport, they have at least one bit that is not in common
    // 

    int discriminating_bit= xor_residual & (-xor_residual);

    assert(discriminating_bit!=0);

    int airport_codes[2]= { xor_residual, xor_residual };
    int src_count[2]= { 0, 0 };
    int dst_count[2]= { 0, 0 };

    for (const ticket *current_ticket= tickets, *end_ticket= tickets + ticket_count; current_ticket!=end_ticket; ++current_ticket)
    {
        int src_index= get_airport_bucket_index(current_ticket->src, discriminating_bit);

        airport_codes[src_index]^= current_ticket->src;
        src_count[src_index]+= 1;

        int dst_index= get_airport_bucket_index(current_ticket->dst, discriminating_bit);
        airport_codes[dst_index]^= current_ticket->dst;
        dst_count[dst_index]+= 1;
    }

    assert((airport_codes[0]^airport_codes[1])==xor_residual);
    assert(abs(src_count[0]-dst_count[0])==1); // all airports with the bit set/unset will be accounted for as well as either the source or destination
    assert(abs(src_count[1]-dst_count[1])==1);
    assert((src_count[0]-dst_count[0])==-(src_count[1]-dst_count[1]));

    int src_index= src_count[0]-dst_count[0]<0 ? 0 : 1; 
    // if src < dst, that means we put more dst into the source bucket than dst, which means the initial source went into the other bucket, which means it should be equal to this bucket!

    assert(get_airport_bucket_index(airport_codes[src_index], discriminating_bit)!=src_index);

    *out_src= airport_codes[src_index];
    *out_dst= airport_codes[!src_index];

    return;
}

int main()
{
    ticket test0[]= { { 1, 2 } };
    ticket test1[]= { { 1, 2 }, { 2, 3 } };
    ticket test2[]= { { 1, 2 }, { 2, 3 }, { 3, 4 } };
    ticket test3[]= { { 2, 3 }, { 3, 4 }, { 1, 2 } };
    ticket test4[]= { { 2, 1 }, { 3, 2 }, { 4, 3 } };
    ticket test5[]= { { 1, 3 }, { 3, 5 }, { 5, 2 } };

    int initial_src, final_dst;

    find_trip_endpoints(test0, sizeof(test0)/sizeof(*test0), &initial_src, &final_dst);
    assert(initial_src==1);
    assert(final_dst==2);

    find_trip_endpoints(test1, sizeof(test1)/sizeof(*test1), &initial_src, &final_dst);
    assert(initial_src==1);
    assert(final_dst==3);

    find_trip_endpoints(test2, sizeof(test2)/sizeof(*test2), &initial_src, &final_dst);
    assert(initial_src==1);
    assert(final_dst==4);

    find_trip_endpoints(test3, sizeof(test3)/sizeof(*test3), &initial_src, &final_dst);
    assert(initial_src==1);
    assert(final_dst==4);

    find_trip_endpoints(test4, sizeof(test4)/sizeof(*test4), &initial_src, &final_dst);
    assert(initial_src==4);
    assert(final_dst==1);

    find_trip_endpoints(test5, sizeof(test5)/sizeof(*test5), &initial_src, &final_dst);
    assert(initial_src==1);
    assert(final_dst==2);

    return 0;
}