一尘不染

单程飞行问题

algorithm

您将进行一次单程间接飞行,其中包括 数十亿次 未知的非常大量 的转机。

  • 您不会在同一机场停两次。
  • 您的旅行的每一部分都有一张票。
  • 每张票都包含 srcdst 机场。
  • 您所拥有的所有门票都是随机排序的。
  • 您忘记了最初的出发机场(第一个来源)和目的地(最后一个目的地)。

设计一种算法,以最小的big- O 复杂性重建您的旅程。


为了解决这个问题,我开始使用两组Srcs和Dsts
对称差

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

但我想必须有另一种更有效的方法。


阅读 258

收藏
2020-07-28

共1个答案

一尘不染

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

<key,value> = <airport, count>

如果机场是源或目的地,则机场的计数会增加。因此,对于每个机场,计数为2(src为1,dst为1),而旅行的来源和目的地除外,计数为1。

您需要至少看一次每张票。因此复杂度为O(n)。

2020-07-28