单程飞行旅行问题-Java 学习之路

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

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

设计一种算法，以最小的复杂度重建您的旅行 .

试图解决这个问题我已经开始使用两个集合symmetric difference，Srcs和Dsts：

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

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

17 回答

10
放入两个哈希：to_end = src - > des; to_beg = des - > src

选择任何机场作为起点S.
```
while(to_end[S] != null)
   S = to_end[S];
```
S现在是您的最终目的地 . 重复其他 Map 以找到您的起点 .

如果没有正确检查，只要你有一个像样的哈希表实现，这就会感觉到O（N） .
回复于 2024-04-29T21:26:05+08:00
5
先决条件

首先，创建一些包含路径一部分的子网结构 .

例如，如果您的完整行程是 a-b-c-d-e-f-g ，则子行程可能是 b-c-d ，即行程的连接子路径 .

现在，创建两个哈希表，将城市映射到包含城市的子网结构 . 因此，一个Hashtable代表一个子网开始的城市，另一个代表一个子网末尾的城市 . 这意味着，一个城市最多可以在其中一个哈希表中出现一次 .

正如我们稍后将看到的，并非每个城市都需要存储，而只需要存储每个子网的开头和结尾 .

构建子条带

现在，一张接一张地买票 . 我们假设票证从 x 到 y （由 (x,y) 表示） . 检查， x 是一些子带 s 的结束（因为每个城市只访问过一次，它不能再是另一个子带的结束） . 如果 x 是开头，只需在子网 s 的末尾添加当前票据 (x,y) . 如果没有以 x 结尾的子带，请检查是否存在以 y 开头的子带 t . 如果是这样，请在 t 的开头添加 (x,y) . 如果还没有这样的子带 t ，只需创建一个仅包含 (x,y) 的新子带 .

应该使用一些特殊的“技巧”来处理子条带 .
- 创建包含 (x,y) 的新子带 s 应将 x 添加到"subtrip beginning cities"的哈希表中，并将 y 添加到"subtrip ending cities"的哈希表中 .
- 在子路径 s=(y,...) 的开头添加新票证 (x,y) ，应从起始城市的哈希表中删除 y ，而是将 x 添加到起始城市的哈希表中 .
- 在子网 s=(...,x) 末尾添加新票证 (x,y) ，应从结束城市的哈希表中删除 x ，而是将 y 添加到结束城市的哈希表中 .
利用这种结构，对应于城市的子条带可以在摊销的O（1）中完成 .

完成所有门票后，我们有一些子订单 . 请注意，在此过程之后，我们最多只有 (n-1)/2 = O(n) 这样的子条带 .

连接子条

现在，我们只是一个接一个地考虑子条带 . 如果我们有一个子带 s=(x,...,y) ，我们只需查看结束城市的哈希表，如果有一个以 x 结尾的子带 t=(...,x) . 如果是这样，我们将 t 和 s 连接到一个新的子程序 . 如果没有，我们知道， s 是我们的第一个子带;然后，我们看，如果有另一个以 y 开头的子带 u=(y,...) . 如果是这样，我们连接 s 和 u . 我们这样做直到只剩下一个子程序（这个子程序就是我们整个原始行程） .

我希望我没有忽视somtehing，但这个算法应该运行：
- 构造所有子条带（最多 O(n) ）可以在 O(n) 中完成，如果我们在 O(1) 中实现向子带添加票据 . 如果我们有一些漂亮的指针结构或类似的东西（将子条带实现为链表），这应该没问题 . 同样更改哈希表中的两个值是（已摊销） O(1) . 因此，此阶段消耗 O(n) 时间 .
- 连接子条直到只留下一个也可以在 O(n) 中完成 . 太看到这一点，我们只需要看看在第二阶段完成了什么：Hashtable查找，需要分摊 O(1) 和可以在 O(1) 中使用指针连接或其他东西完成的子程序连接 .
因此，整个算法需要时间 O(n) ，这可能是最佳的 O -bound，因为至少可能需要查看每个票证 .
回复于 2024-04-29T21:26:05+08:00
1
不需要哈希或类似的东西 . 这里的实际输入大小不一定是票证的数量（比如说n），而是票据的总数'size'（比如N），编码所需的总数 char .

如果我们有一个k个字符的字母表（这里k大约是42个），我们可以使用bucketsort技术排序总长度为N的n个字符串的数组，这些字符串在O（n N k）时间内用k个字符的字母表编码 . 如果n <= N（平凡）且k <= N（井N为数十亿，不是），则以下情况有效
- 按照票证的顺序，从票证中提取所有机场代码并将其存储在 struct 中，其中代码为字符串，票证索引为数字 .
- 根据代码对 struct 的数组进行Bucketsort
- 运行已排序的数组并为每个新遇到的航空公司代码分配一个序号（从0开始） . 对于具有相同代码的所有元素（它们是连续的）转到票证（我们已将号码与代码一起存储）并将票证的代码（选择权利， src 或 dst ）更改为序号 .
- 在此运行期间，我们可以识别原始源 src0 .
- 现在所有故障单都将 src 和 dst 重写为序号，故障单可以解释为从 src0 开始的一个列表 .
- 在票证上进行列表排名（= toplogical sort，跟踪 src0 的距离） .
回复于 2024-04-29T21:26:05+08:00
0

在我看来，基于图形的方法就是基于此 .

每个机场都是一个节点，每张机票都是一个优势 . 让我们现在的每个边缘都是无向的 .

在第一阶段，您将构建图形：对于每个故障单，您可以查找源和目标，并在它们之间构建边缘 .

现在构建了图形，我们知道它是非周期性的，并且通过它只有一条路径 . 毕竟，你只有自己旅行的机票，而且你曾经没有去过同一个机场 .

在第二阶段，您正在搜索图表：选择任何节点，并在两个方向上启动搜索，直到您发现无法继续 . 这些是您的来源和目的地 .

如果您需要明确说明哪个是源，哪个是目标，请为每个边添加一个目录属性（但保留一个无向图） . 获得候选源和目标后，您可以根据连接到它们的边缘确定哪个是哪个 .

该算法的复杂性取决于查找特定节点所花费的时间 . 如果你可以达到O（1），那么时间应该是线性的 . 你有n个票，所以你需要O（N）步骤来构建图，然后O（N）搜索和O（N）重建路径 . 还是O（N） . 邻接矩阵会给你这个 .

如果你不能节省空间，你可以为节点做一个哈希，这会给你O（1）最佳散列和所有那些废话 .

回复于 2024-04-29T21:26:05+08:00
20

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

构造哈希表需要O（n）并且构造列表需要O（n），因此整个算法是O（n） .

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

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

回复于 2024-04-29T21:26:05+08:00
0

每个机场都是 node . 每张票都是 edge . 创建一个邻接矩阵来表示图形 . 这可以作为压缩边缘的位字段来完成 . 您的起点将是没有路径的节点（它的列将为空） . 一旦你知道这一点，你只需按照现有的路径 .

或者，您可以 Build 一个可由机场索引的结构 . 对于每张票，你查找它是 src 和 dst . 如果找不到，则需要在列表中添加新机场 . 当找到每一个时，你设置一个出发机场's exit pointer to point to the destination, and the destination'的到达指针指向出发机场 . 当您没有票时，您必须遍历整个列表以确定谁没有路径 .

另一种方法是拥有一个可变长度的迷你旅行列表，您可以在遇到每张票时将它们连接在一起 . 每次添加票证时，您都会看到任何现有迷你旅行的结尾是否与您的票证的src或dest相匹配 . 如果没有，那么您当前的机票将成为它自己的迷你旅行并被添加到列表中 . 如果是这样的话，那么新票将被添加到它匹配的现有旅行的末尾，可能将两个现有的迷你旅行拼接在一起，在这种情况下，它会将迷你旅行列表缩短一个 .

回复于 2024-04-29T21:26:05+08:00

我编写了一个小的python程序，使用两个哈希表一个用于计数，另一个哈希表用于src到dst映射 . 复杂性取决于字典的实现 . 如果字典有O（1）那么复杂度是O（n），如果字典在STL映射中有O（lg（n）），则复杂度为O（n lg（n））

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 )

回复于 2024-04-29T21:26:05+08:00

3
让我们暂时忘记数据结构和图形 .

首先，我需要指出，每个人都假设没有循环 . 如果路线经过一次机场两次，那么这是一个更大的问题 .

但是现在让我们保持这个假设 .

输入数据实际上已经是有序集 . 每张票都是向一组机场引入订单的关系元素 . （英语不是我的母语，所以这些可能不是正确的数学术语）

每张票都包含如下信息： airportX < airportY ，因此在执行一次票证时，算法可以从任何机场开始重新创建有序列表 .

现在让我们放弃“线性假设” . 不能从那种东西中定义订单关系 . 输入数据必须被视为正式语法的生成规则，其中语法的词汇集是一组ariport名称 . 这样的票：
```
src: A
dst: B
```
实际上是一对制作：
```
A->AB
B->AB
```
你只能保留一个 .

现在你必须生成每一个可能的句子，但您可以使用每个生产环境规则一次 . 仅使用其每个产品一次的最长句子是正确的解决方案 .
回复于 2024-04-29T21:26:05+08:00
0
如果您假设可以存储所有内容的可连接列表结构（可能存储在磁盘上）：
- 创建2个空哈希表S和D.
- grab 第一个元素
- 在D中查找其src
- 如果找到，从D中删除关联的节点并将其链接到当前节点
- 如果未找到，请将节点插入S键上的S键
- 从另一个方向重复src < - > des，S < - > D.
- 从下一个节点重复2 .
O(n) 时间 . 至于空间，birthday paradox（或类似的东西）将使您的数据集比整个集小很多 . 在运气不好的情况下它仍然变大（最坏的情况是 O(n) ），你可以从哈希表中逐出随机运行并将它们插入到处理队列的末尾 . 你的速度可以用到底池，但是只要你可以远远超过threashold预期的冲突（~ O(sqrt(n)) ），你应该期望看到你的数据集（表和输入队列组合）经常缩小 .
回复于 2024-04-29T21:26:05+08:00
0

请注意，如果任务只是确定源机场和目的地机场（而不是重建整个行程），那么拼图可能会变得更有趣 .

即，假设机场代码以整数给出，可以使用O（1）数据传递和O（1）附加存储器来确定源和目的地机场（即，不使用哈希表，排序，二进制搜索等） . ） .

当然，一旦你找到了源码，索引和遍历整个路径也变得微不足道，但从这一点来看，总的来说至少需要O（n）额外的内存（除非你可以对数据进行排序）顺便说一句，它允许在O（n log n）时间内使用O（1）附加内存来解决原始任务

回复于 2024-04-29T21:26:05+08:00

这是单路径状态机矩阵的简单情况 . 抱歉，伪代码是C＃风格，但用对象表达想法更容易 .

首先，构建一个收费公路矩阵 . 在What are some strategies for testing large state machines?阅读我对收费公路矩阵的描述（不要理会FSM答案，只是对收费公路矩阵的解释） .

但是，您描述的限制使案例成为简单的单路径状态机 . 它是完全覆盖的最简单的状态机 .

对于5个机场的简单案例，
vert nodes = src / entry points，
horiz nodes = dst / exit points .

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>>>>

机器有两种模式，

旅行计划 - 您不知道有多少机场，并且您需要针对未指定数量的机场的通用旅行计划
旅行重建 - 您拥有过去旅行的所有收费公路票，但它们都是您手套箱/ Baggage 包中的一大堆 .

我假设你的问题是旅行重建 . 所以，你从那堆票中随机挑选一张票 .

我们假设票堆是无限大小的 .

tak mnx cda 
bom    0
daj       0
phi           0

其中0值表示无序票 . 让我们将无序票证定义为其dst与另一票证的src不匹配的票证 .

以下下一张票证发现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

将existent.dst与new.src匹配
或existent.src到new.dst：

tak cda kul svn xml
bom    0
daj          L1
olm               0
jdk                   0
klm      L2


<bom,tak>, <daj,<mnx,kul>>, <<klm,phi>, cda>

上述拓扑练习仅用于视觉理解 . 以下是算法解决方案 .

这个概念是将有序对聚类到子列表中，以减少我们用来存放票证的哈希结构的负担 . 渐渐地，将会有越来越多的伪票（由合并的匹配票组成），每个伪票都包含一个不断增长的有序目的地子列表 . 最后，将在其子列表中保留一个包含完整行程向量的伪票 .

如您所见，也许最好用Lisp完成 .

但是，作为链接列表和 Map 的练习......

创建以下结构：

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);
  }
}

检查是否存在dst：

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;
}

我有一种感觉，上面有一些错字，但这个概念应该是正确的 . 发现任何错字，有人可以提供帮助纠正它，plsss .

回复于 2024-04-29T21:26:05+08:00

创建两个数据结构：

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
  }
}

回复于 2024-04-29T21:26:05+08:00

29

Summary: below a single-pass algorithm is given . （即，不仅仅是线性的，而且每张票只看一次，这当然是每张票的最佳访问次数） . 我把摘要放在一边，因为有许多看似相同的解决方案，很难发现为什么我添加了另一个 . :)

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

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

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

总而言之，O（N） .

是的，我当场回答:)

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

Edit 2 同样令人感兴趣的是，与使用2个哈希表的解决方案相比，这个解决方案使用了一个带有 at most N / 2个条目的哈希表（如果我们按照第1，第3，第5，等等） . 因此，除了更快之外，这也使用大约一半的内存 .

回复于 2024-04-29T21:26:05+08:00
2
最简单的方法是使用哈希表，但是没有最好的最坏情况复杂性（ O(n2) ）

代替：
- 创建一堆包含（src，dst） O(n) 的节点
- 将节点添加到列表并按src O(n log n) 排序
- 对于每个（目标）节点，在列表中搜索相应的（源）节点 O(n log n)
- 查找起始节点（例如，使用拓扑排序或在步骤3中标记节点） O(n)
总体而言： O(n log n)

（对于这两种算法，我们假设字符串的长度可以忽略不计，即比较为O（1））
回复于 2024-04-29T21:26:05+08:00

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

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

编辑2：假设每个机场都有使用三字符代码的票证，您可以使用此处描述的算法（Find three numbers appeared only once）通过将所有机场连接在一起来确定两个独特的机场 .

EDIT3：这是使用xor方法实际解决这个问题的一些C.假设从机场到整数的唯一编码（假定使用三字母机场代码或使用纬度和经度将机场位置编码为整数），整个算法如下：

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

接下来，设置两个桶，每个桶都具有第一步的XORed值 . 现在，对于每个机票，根据是否设置了指定位设置每个机场，并且xor机场代码与桶中的值 . 还要跟踪每个桶有多少源机场和目的地机场到达该桶 .

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

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;
}

回复于 2024-04-29T21:26:05+08:00

0

哈希表不适用于大尺寸（例如原始问题中的数十亿）;任何与他们合作过的人都知道他们只适合小套装 . 您可以使用二叉搜索树，这将给您复杂性O（n log n） .

最简单的方法是两次传递：第一次将它们全部添加到树中，由src索引 . 第二个遍历树并将节点收集到一个数组中 .

我们可以做得更好吗？如果我们真的想要，我们可以：我们可以一次完成 . 将每个故障单表示为喜欢列表中的节点 . 最初，每个节点都有下一个指针的空值 . 对于每个故障单，请在索引中输入其src和dest . 如果完成了's a collision, that means that we already have the adjacent ticket; connect the nodes and delete the match from the index. When you'，你将只进行一次传递，并且有一个空索引，并且按顺序排列所有票证的链接列表 .

这种方法明显更快：它只有一次，而不是两次;并且存储明显更小（最坏情况：n / 2;最佳情况：1;典型情况：sqrt（n）），足以使您可以实际使用哈希而不是二叉搜索树 .

回复于 2024-04-29T21:26:05+08:00
2

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

<key,value> = <airport, count>

如果机场是源头或目的地，机场的数量会增加 . 因此，对于每个机场，计数将为2（src为1，dst为1），除了旅行的来源和目的地，计数为1 .

您需要至少查看一次每张票 . 所以复杂性是O（n） .

回复于 2024-04-29T21:26:05+08:00

单程飞行旅行问题

17 回答

先决条件

构建子条带

连接子条

相关问题