您将进行一次单程间接飞行,其中包括 数十亿次 未知的非常大量 的转机。
设计一种算法,以最小的big- O 复杂性重建您的旅程。
为了解决这个问题,我开始使用两组Srcs和Dsts 的对称差:
1)对数组Srcs中的所有src键进行 排序2)对数组Dsts中的所有dst键进行排序 3)创建两个数组的并集以查找非重复项-它们是您的第一个src和最后一个dst 4)现在,有了起点,使用二进制搜索遍历两个数组。
但我想必须有另一种更有效的方法。
构造一个哈希表,并将每个机场添加到哈希表中。
<key,value> = <airport, count>
如果机场是源或目的地,则机场的计数会增加。因此,对于每个机场,计数为2(src为1,dst为1),而旅行的来源和目的地除外,计数为1。
您需要至少看一次每张票。因此复杂度为O(n)。