顺便说一句，目前还不清楚您的第二个解决方案如何实现 O （| B |）。扫描 B 时，如何“获取出现在 A 中的元素”？听起来某处应该有一个对数 A 因素。

我能提供的最好的是一种离线算法，该算法对 O （| B | + L ），其中 L 是所有 A 长度的总和。 “离线”是指您可以提前阅读所有 A 。

1. 预处理 B 并构建一个哈希表，将 B 中的值映射到它们的位置。对于您的示例，哈希表是（1-> 1，2-> 2，4-> 3，5-> 4，7-> 5，8-> 6，9-> 7）。
2. 为 B 中的每个元素存储一个链表，起初为空。
3. 扫描所有 A 。如果 A_i [ j ] = k ，则将 i 附加到 k 的链接列表中em>。我们可以使用哈希表快速找到 k 的链接列表（也就是 B 中 k 的位置）。在您的示例中，假设 A 是我们从输入中读取的第一个向量，并且由于 A _1 [4] = 8，我们将1附加到链表8中。 B 。
4. 刷新 A 数组。
5. 扫描 B 并将元素推入 A 数组。例如，如果链表8包含值1、4和20，则在第1、4和20数组中推入值8。

实际上，这是一个记忆猪。您对10 ^ 10 64位数字的约束已经假定80 GB的可用RAM。哈希表至少需要该数量的三倍。将所有 A 存储在内存和链接列表中还至少需要3个 L 64位值。

我非常怀疑是否存在一种实用的在线算法，该算法可以很好地利用 B 一次处理一个 A 。即使假设您可以在O（1）的 B 中查找位置（例如，使用哈希表），也会将 A 中元素的范围从64位缩小为34（向上取整10 ^ 10）。因此计数排序仍然不可用，因为最后一步需要扫描10 ^ 10值的域以对10 ^ 5元素数组进行排序。离线算法的作用本质上是通过一次对所有阵列进行排序来进行大规模扫描的结果。