您将进行一次单程间接飞行旅行，其中包括数十亿一个未知的非常大的数字个转机。
设计一种算法，以最小的大O复杂度重建您的旅程。
尝试解决这个问题，我开始使用两个集合Srcs和Dsts的对称差异：
1）在数组Srcs中对所有src键进行排序
2）在数组Dsts中对所有dst键进行排序
3）创建一个联合集，以查找非重复项——它们是您的第一个Src和最后一个Dst
4）现在，有了起点，使用二进制搜索遍历两个数组。
但我认为可能有另一种更有效的方法。
构建散列表并将每个机场添加到散列表中。
<key,value> = <airport, count>
如果机场是源或终点，则该机场的计数会增加。因此，对于每个机场，计数将为2（源和目的地各1），但是对于您旅行的起点和终点，计数将为1。
您需要至少查看每张机票一次。因此，时间复杂度为O(n)。
摘要：下面给出了一种单遍算法（即不仅是线性的，而且每张票只会考虑一次，这当然是每张票最理想的访问次数）。我放了这个摘要是因为有许多看起来相等的解决方案，很难发现我为什么还要添加另一个 :)
实际上，我在面试中被问到了这个问题。这个概念非常简单：每张机票都是一个单例列表，具有概念上的两个元素：起点和终点。
我们使用其第一个和最后一个元素作为键，在哈希表中对每个这样的列表进行索引，以便我们可以在O(1)时间内找到列表是否以特定元素（机场）开头或结尾。对于每张机票，当我们看到它从另一个列表结束的地方开始时，只需链接这些列表（O(1)）。同样，如果它在另一个列表开始的地方结束，那就连接另一个列表。当然，当我们链接两个列表时，我们基本上破坏了这两个列表并得到了一个列表。（N张机票的链将在N-1个这样的链接之后构建）。
需要注意的是，必须保持哈希表键正好是剩余列表的第一个和最后一个元素的不变式。
总体而言，时间复杂度为O(N)。
没错，我当场就回答了这个问题 :)
编辑 忘记添加一个重要的点。每个人都提到两个哈希表，但一个哈希表也可以解决问题，因为算法的不变式包括任何单个城市（如果有两个，我们立即将它们链接在一起，并从哈希表中删除该城市）的起始或结束处最多只能有一个机票列表。从渐近意义上讲，没有区别，只是这种方式更简单。
编辑2 还有一个有趣的事实，与使用每个具有N个条目的2个哈希表的解决方案相比，该解决方案使用最多N/2个条目的一个哈希表（如果我们以1、3、5等顺序查看机票，则会发生这种情况）。因此，这也使用了大约一半的内存，除了更快之外。
<src，dst>还是一种具有两个单独哈希函数的多维哈希集？因为我不明白如何使用联合哈希键搜索特定的src和任意的dst。考虑我们想要连接一个航班<src=s，dst=d>，那么我们必须在现有序列上执行两次查找：<src=d，_>和<_, dst=s>，对吗？你在这里想到了什么样的哈希函数？ - bluenote10struct 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;
}
Route
{
start
end
list of flights where flight[n].dest = flight[n+1].src
}
List of Routes
然后：
foreach (flight in random set)
{
added to route = false;
foreach (route in list of routes)
{
if (flight.src = route.end)
{
if (!added_to_route)
{
add flight to end of route
added to route = true
}
else
{
merge routes
next flight
}
}
if (flight.dest = route.start)
{
if (!added_to_route)
{
add flight to start of route
added to route = true
}
else
{
merge routes
next flight
}
}
}
if (!added to route)
{
create route
}
}
输入两个哈希表：
to_end = src -> des;
to_beg = des -> src
选择任意一个机场作为起点S。
while(to_end[S] != null)
S = to_end[S];
S现在是你的最终目的地。使用另一张地图重复此步骤以找到你的起点。
如果没有适当的检查，这可能会感觉像O(N)，前提是你有一个不错的哈希表实现。
A1 A2 A3 A4 A5
A1 x
A2 x
A3 x
A4 x
A5 x
请注意，对于每一行和每一列，都不应该有超过一个转换。
要获取机器的路径，您需要将矩阵排序为
A1 A2 A3 A4 A5
A2 x
A1 x
A3 x
A4 x
A5 x
A1 A2 A3 A4 A5
A2 x
A5 x
A1 x
A3 x
A4 x
有序对列表为：
a2:a1，a5:a2，a1:a3，a3:a4，a4:a5。
或者更正式地表示为：
<a2,a1>, <a5,a2>, <a1,a3>, <a3,a4>, <a4,a5>.
嗯...有序对？在Lisp中闻到了递归的味道？
<a2,<a1,<a3,<a4,a5>>>>
这个机器有两种模式：
我猜你的问题是关于旅行重建的。所以，你可以从那堆票中随机挑选一张接一张地查看。
我们假设票堆的大小是无限的。
tak mnx cda
bom 0
daj 0
phi 0
当数值为0时，表示未排序的票。我们将未排序的票定义为其目的地与另一张票的出发地不匹配的票。
接下来的票发现mnx(dst) = kul(src)匹配。
tak mnx cda kul
bom 0
daj 1
phi 0
mnx 0
当您选择下一个机票时，有可能连接两个连续的机场。如果发生这种情况，您将从这两个节点创建一个群集节点：
<bom,tak>, <daj,<mnx,kul>>
矩阵被简化，
tak cda kul
bom 0
daj L1
phi 0
在哪里
L1 = <daj,<mnx,kul>>
这是主列表的子列表。
继续挑选下一个随机票。
tak cda kul svn xml phi
bom 0
daj L1
phi 0
olm 0
jdk 0
klm 0
将现有的目标地址匹配到新的源地址
或将现有的源地址匹配到新的目标地址：
tak cda kul svn xml
bom 0
daj L1
olm 0
jdk 0
klm L2
<bom,tak>, <daj,<mnx,kul>>, <<klm,phi>, cda>
class Ticket:MapEntry<src, Vector<dst> >{
src, dst
Vector<dst> dstVec; // sublist of mergers
//constructor
Ticket(src,dst){
this.src=src;
this.dst=dst;
this.dstVec.append(dst);
}
}
class TicketHash<x>{
x -> TicketMapEntry;
void add(Ticket t){
super.put(t.x, t);
}
}
TicketHash<src>{
src -> TicketMapEntry;
void add(Ticket t){
super.put(t.src, t);
}
}
TicketHash<dst>{
dst -> TicketMapEntry;
void add(Ticket t){
super.put(t.dst, t);
}
}
TicketHash<dst> mapbyDst = hash of map entries(dst->Ticket), key=dst
TicketHash<src> mapbySrc = hash of map entries(src->Ticket), key=src
当从堆中随机选取一张票时，
void pickTicket(Ticket t){
// does t.dst exist in mapbyDst?
// i.e. attempt to match src of next ticket to dst of an existent ticket.
Ticket zt = dstExists(t);
// check if the merged ticket also matches the other end.
if(zt!=null)
t = zt;
// attempt to match dst of next ticket to src of an existent ticket.
if (srcExists(t)!=null) return;
// otherwise if unmatched either way, add the new ticket
else {
// Add t.dst to list of existing dst
mapbyDst.add(t);
mapbySrc.add(t);
}
}
检查目标是否存在：
Ticket dstExists(Ticket t){
// find existing ticket whose dst matches t.src
Ticket zt = mapbyDst.getEntry(t.src);
if (zt==null) return false; //no match
// an ordered pair is matched...
//Merge new ticket into existent ticket
//retain existent ticket and discard new ticket.
Ticket xt = mapbySrc.getEntry(t.src);
//append sublist of new ticket to sublist of existent ticket
xt.srcVec.join(t.srcVec); // join the two linked lists.
// remove the matched dst ticket from mapbyDst
mapbyDst.remove(zt);
// replace it with the merged ticket from mapbySrc
mapbyDst.add(zt);
return zt;
}
Ticket srcExists(Ticket t){
// find existing ticket whose dst matches t.src
Ticket zt = mapbySrc.getEntry(t.dst);
if (zt==null) return false; //no match
// an ordered pair is matched...
//Merge new ticket into existent ticket
//retain existent ticket and discard new ticket.
Ticket xt = mapbyDst.getEntry(t.dst);
//append sublist of new ticket to sublist of existent ticket
xt.srcVec.join(t.srcVec); // join the two linked lists.
// remove the matched dst ticket from mapbyDst
mapbySrc.remove(zt);
// replace it with the merged ticket from mapbySrc
mapbySrc.add(zt);
return zt;
}
检查是否存在src：
Ticket srcExists(Ticket t){
// find existing ticket whose src matches t.dst
Ticket zt = mapbySrc.getEntry(t.dst);
if (zt == null) return null;
// if an ordered pair is matched
// remove the dst from mapbyDst
mapbySrc.remove(zt);
//Merge new ticket into existent ticket
//reinsert existent ticket and discard new ticket.
mapbySrc.getEntry(zt);
//append sublist of new ticket to sublist of existent ticket
zt.srcVec.append(t.srcVec);
return zt;
}
我感觉以上内容有很多错别字，但概念应该是正确的。如果发现任何错误，请请求帮助进行更正。
import random
# actual journey: a-> b -> c -> ... g -> h
journey = [('a','b'), ('b','c'), ('c','d'), ('d','e'), ('e','f'), ('f','g'), ('g','h')]
#shuffle the journey.
random.shuffle(journey)
print("shffled journey : ", journey )
# Hashmap to get the count of each place
map_count = {}
# Hashmap to find the route, contains src to dst mapping
map_route = {}
# fill the hashtable
for j in journey:
source = j[0]; dest = j[1]
map_route[source] = dest
i = map_count.get(source, 0)
map_count[ source ] = i+1
i = map_count.get(dest, 0)
map_count[ dest ] = i+1
start = ''
# find the start point: the map entry with count = 1 and
# key exists in map_route.
for (key,val) in map_count.items():
if map_count[key] == 1 and map_route.has_key(key):
start = key
break
print("journey started at : %s" % start)
route = [] # the route
n = len(journey) # number of cities.
while n:
route.append( (start, map_route[start]) )
start = map_route[start]
n -= 1
print(" Route : " , route )
- 按照出发时间排序机票
- 第一张机票的起点是您的出发机场，最后一张机票的到达点是您的到达机场。 ;)
- Nick Johnson