给定n个元素的排序数组,在​​线性时间内对n/2个元素进行排序

Question

我有一个n元素的排序数组.现在我给了n/2个元素,每个元素都属于排序数组.n/2个元素是从排序数组中随机获取的.如何在线性时间内对这些n/2元素进行排序？

Answer 1

一种方法涉及散列.构建一个包含从数组中提取的所有n/2个元素的哈希集.如果允许重复,则从元素到其频率构建哈希表.这将需要O(n)时间,在期望.

然后,按升序迭代排序的数组,并且对于数组的每个元素,检查它是否在哈希集/哈希表中.如果是这样,请将该元素附加到输出数组(如果允许重复,则在集合中每个元素的副本执行一次).对于数组的每个元素,这将在期望上花费O(1)时间,因此该步骤也需要时间O(n).

因此,总运行时间为O(n),符合预期.

希望这可以帮助!