algorithm - 计算数组中的值 "surround"数组外的不同值

Question

假设我们有一个具有 n 个不同值的排序整数数组 A，并且给定了一些不包含在 A 中的值 M。

例如:A = [2,3,5,8,10]，M = 4。该问题要求我们找到与 M 相关的 x“周围值”，其中 x 将是从 1 到 n 的偶数。如果 x 是 2，我们将返回 [3,5]。如果 x 为 4，则返回 [2,3,5,8]。这个过程对我来说很有意义，我们实际上是如何在排序数组中找到 M 的位置，并在我们递增 x 时获取两边的值，并且很明显可以看到如何在线性时间内完成此操作。但是，如果初始数组实际上没有排序并且仍然遵循相同的输入和输出要求怎么办。

例如，如果 A 为 A = [8,5,10,2,3]，并且 M = 4，则将 x 设置为 2 仍应返回 [3,5]。有一个线性时间算法可以解决它，但是如果有人可以提供一些非常有帮助的指示或方向。我考虑过计数排序，但我们不知道整数的最大大小，所以我觉得在这种情况下使用它并不明智。

Answer 1

这在 O(n) 时间内是可能的。创建两个列表:一个包含数组中所有大于 M 的元素，另一个包含数组中所有小于 M 的元素。现在使用 selection algorithm在 larger_than_list 和 (|smaller_than_list| - x/2) 中找到第 x/2 个最小元素 小于_列表。 Prune名单。