algorithm - 在 O(n) 时间内确定序列 T 是否是序列 S 的排序

Question

我知道可以很容易地确定一个序列是否在 O(n) 时间内排序。然而，我们如何确保某个序列 T 确实是在 O(n) 时间内对序列 S 中的元素进行排序？

也就是说，有人可能有一个算法可以输出一些确实按排序顺序排列的序列 T，但可能不包含序列 S 中的任何元素，那么我们如何检查 T 确实是 O( n) 时间？

Answer 1

1. 获取S的长度L。
2. 还要检查T 的长度。如果它们不同，你就完成了!
3. 设 Hs 是一个 HashMap ，其中包含 S 中所有元素的 2L 个桶。
4. 设 Ht 为 T 中所有元素的 HashMap (同样，具有 2L 桶)。
5. 对于 T 中的每个元素，检查它是否存在于 Hs 中。
6. 对于 S 中的每个元素，检查它是否存在于 Ht 中。

如果元素在每个序列中都是唯一的，这将起作用。请参阅 wcdolphin 的回答，了解使其适用于非唯一序列所需的小改动。

我没有考虑内存消耗。创建两个每个序列大小加倍的 hashmap 可能很昂贵。这是速度和内存之间的通常权衡。