问题描述
您要转帐的一个单向的间接飞行之旅，包括十亿的未知的大量的。
You are going on a one-way indirect flight trip that includes an unknown very large number of transfers.
- 您是不是在同一个机场停两次。
- 您有1票为您的旅行的每一个部分。
- 在每张门票中包含的 SRC 和 DST 机场。
- 所有门票已被随机排序。
- 您忘记了原来的出发机场（第一个SRC）和目的地（最后DST）。
- You are not stopping twice in the same airport.
- You have 1 ticket for each part of your trip.
- Each ticket contains src and dst airport.
- All the tickets you have are randomly sorted.
- You forgot the original departure airport (very first src) and your destination (last dst).
设计一个算法来重建您以最小的大端之旅的 0 的复杂性。
Design an algorithm to reconstruct your trip with minimum big-O complexity.
试图解决这个问题，我已经开始使用两套，分区域协调员和DSTS一个对称差：
Attempting to solve this problem I have started to use a symmetric difference of two sets, Srcs and Dsts:
1）在阵列索马里红新月
排序的所有SRC键2）在阵列DSTS排序的所有DST键
3）创建并集两个阵列来寻找非重复的 - 他们是你的第一个src和最后DST
4）现在，其出发点，采用二进制搜索遍历两个数组。
1)Sort all src keys in array Srcs
2)Sort all dst keys in array Dsts
3)Create an union set of both arrays to find non-duplicates - they are your first src and last dst
4)Now, having the starting point, traverse both arrays using the binary search.
不过，我想一定有另一种更有效的方法。
But I suppose there must be another more effective method.
推荐答案
构造一个哈希表，并添加每个机场到哈希表。
Construct a hashtable and add each airport into the hash table.
＆LT;键，值GT; =＆LT;机场，算上＆GT;
计数为机场增加，如果机场是源或目标。因此，对于每一个机场的数量将是2（1 src和1 DST）除源和您的旅行目的地，将有计数为1。
Count for the airport increases if the airport is either the source or the destination. So for every airport the count will be 2 ( 1 for src and 1 for dst) except for the source and the destination of your trip which will have the count as 1.
您需要看每张票至少一次。所以复杂度为O（n）。
You need to look at each ticket at least once. So complexity is O(n).
这篇关于单程飞行之旅的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！