algorithm - 大小为 n 的数组中缺少 m 个整数

Question

这是我前一段时间遇到的一个有趣的问题，但在解决它时遇到了一些困难。

There's an unsorted integer array of size N stored with numbers 1,2..,N+M , with M integers missing from it. M and N are known before hand. Write an algorithm to find the missing M integers in the most efficient manner.

已尝试将其映射到大小为 N + M 的数组，以便第 i 个索引包含值为 i，但这需要 2 次扫描(1 次用于映射，1 次用于查找 M 缺失的数字)。

我在其中遇到此问题的那本书提到了一个单一的扫描解决方案是可能的，但我无法实现它。关于如何解决这个问题的任何想法？

Answer 1

您可以使用映射到数组顶部的双向链表来做到这一点。

position 1 2 3 4 5 6 ...
next     2 3 4 5 6 7 ...
prev     0 1 2 3 4 5 ...

在通过输入时，您索引到与每个输入数字对应的位置并更新链接列表以从链接列表中删除(跳过)该位置。在输入结束时，链表将仅包含未访问的位置。